Give a number n, find the minimum x 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.
#include <iostream> using namespace std; #include<cmath> class Fn { public: int X(int n) { if (n == 1) return 0; if (n % 2 == 0 && n != 2) return -1; int x = 1; long long a = 2; while (a % n != 1) { x++; a = (a * 2) % n; if (a== 0) return -1; if (x > n) return -1; } return x; } }; int main() { Fn b; int n; while (cin >> n) { int x = b.X(n); if (x != -1) { cout << "2^" << x << " mod " << n << " = 1" << endl; } else { cout << "2^? mod " << n << " = 1" << endl; } } return 0; }
