ORIGIN

HDU-1395 2^x mod n=1

ACM 1 mins211 words

HDU-1395 2x mod n=1

Give a number n, find the minimum x(x>0) that satisfies 2^x mod n = 1.

Input

One positive integer on each line, the value of n.

Output

If the minimum x exists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replace x and n with specific numbers.

Sample Input

1
2
2
5

Sample Output

1
2
2^? mod 2 = 1
2^4 mod 5 = 1

Analysis

This is a loop problem, you need to loop x from 1 to MAX to find if there is an x that fits it. However, if the $2^{MAX}$ can be very big and exceeded long long. So we use an formula
$$
(a \times b)%n = ((a % n) \times b) % n
$$
which means $2^i = (2^i ) % n$ in this situation.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>

using namespace std;

int main() {
int n;
while(cin >> n) {
int i = 1, ans = 2;
for(; i < 10000; i ++) {
if(ans % n == 1) break;
ans *= 2;
ans %= n;
}
if(i < 10000) printf("2^%d mod %d = 1\n", i, n);
else printf("2^? mod %d = 1\n", n);
}
return 0;
}
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|