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
PLAINTEXT
1 2
2 5
Sample Output
PLAINTEXT
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 2MAX can be very big and exceeded long long. So we use an formula (a×b)
which means 2i=(2i) in this situation.
Code
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
#include<bits/stdc++.h>
usingnamespace std;
intmain(){ 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); elseprintf("2^? mod %d = 1\n", n); } return0; }
