欧拉定理,可暴力。题意:给一个整数n求满足2^x = 1(mod n)的最小x(x > 1)。
我的解题思路:根据欧拉定理及其推广,当n与2互素时2^phi(n) = 1(mod n),因此容易得知当n为奇数时n与2互素。当n为偶数或者1时则必定不能满足2^x = 1(mod n)。另外,当n与2互素时phi(n)不一定是满足要求的最小x,但是根据欧拉定理的推广,最小x必定能整除phi(n),因此枚举phi(n)的因子就可以了。
我的解题代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> using namespace std; typedef long long Long; Long n; Long FastPow(Long base, Long n, Long mod); Long Phi(Long x); int main() { while (~scanf("%lld", &n)) { if (n % 2 == 0 || n == 1) { printf("2^? mod %lld = 1\n", n); continue; } Long temp = Phi(n); for (Long i=2; i<=temp; ++i) { if (temp % i != 0) continue; //G++下加了这句就60+ms,不加就700+ms,Orz if (FastPow(2, i, n) == 1) { printf("2^%lld mod %lld = 1\n", i, n); break; } } } return 0; } Long FastPow(Long base, Long n, Long mod) { Long ans = 1; base %= mod; while (n) { if (n & 1) { ans *= base; ans %= mod; } base *= base; base %= mod; n >>= 1; } return ans; } Long Phi(Long x) { Long ans = x; Long cnt = (Long)sqrt(x + 0.5) + 1; for (Long i=2; i<cnt; ++i) { if (x % i == 0) { while (x % i == 0) x /= i; ans -= ans / i; } } if (x > 1) ans -= ans / x; return ans; }