hdu 4910 Problem about GCD
表示完全给跪了,打表找规律+大数值的素数检测。可参见这篇博客:HDU
4910 Problem about GCD(米勒拉宾)
Miller Rabin算法就是基于概率的素数测试算法,利用费马小定理,a^(p-1)%p = 1 {gcd(a,p) = 1 && prime(p)=true},随机多个小于p且大于0的a值,若均检测出p为素数,则可认为p是素数
#include <cstdio> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 1000005; typedef __int64 LL; int vis[MAXN], nprm; LL prim[MAXN]; void init_prime() { for (LL i = 2; i<=1000000LL; ++i) { if (!vis[i]) prim[nprm++] = i; for (int j = 0; j< nprm && prim[j]*i <= 1000000LL; ++j) { vis[i*prim[j]] = 1; if (i%prim[j] == 0) break; } } } /* a*b = a*(2^n*wn + 2^(n-1)*w(n-1) + 2^(n-2)*w(n-2)+ ... +2^0*w0) */ LL mul_mod(LL a, LL b, LL mod) { LL res = 0LL; while (b) { if (b & 1) res = (res+a)%mod; a = (a+a)%mod; b >>= 1; } return res; } LL mpow(LL x, LL nm, LL mod) { LL res = 1; while (nm) { if (nm & 1) res = mul_mod(res, x, mod); x = mul_mod(x, x, mod); nm >>= 1; } return res; } int miller_rabin(LL m) { if (m < 2) return 0; if (m == 2) return 1; if (m % 2 == 0) return 0; for (int i = 0; i< 20; ++i) if (mpow(rand()%(m-1)+1, m-1, m) != 1) return 0; return 1; } int solve(LL n) { if (n % 4 == 0) return 0; if (n % 2 == 0) n /= 2; for (int i = 1; i< nprm; ++i) { LL pp = n; if (pp % prim[i] == 0) { while (pp % prim[i] == 0) pp /= prim[i]; if (pp == 1) return 1; else return 0; } } if (miller_rabin(n)) return 1; LL x = (LL)sqrt(double(n)); if (x*x == n) return 1; return 0; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif init_prime(); LL n; while (~scanf("%I64d", &n) && n!=-1) { LL res; if (n <= 5 || solve(n)) printf("%I64d\n", n-1); else printf("1\n"); } return 0; }