hihocode 第九十二周 数论一·Miller-Rabin质数测试
检测n是否为素数，数据范围为2 <= n <= 10^18;
思路:Miller_Rabin素数检测模板题，原理:在Fetmat定理的基础之上，再利用二次探测定理；
对于任意的正整数p ，如果a^(p-1) % p != 1，则p一定不是素数，否则由Fermat定理，该数为素数的概率大于1/2;而MR检测中把p-1一直检测除以2直到为奇数为止，
由于当p为素数时x^2 % p = 1有x = 1或x = p-1;这样就把每次随机取值为素数的概率降到了1/4;同时Fermat里面还涉及到Carmichael数，这在MR检测中不存在；
ps:开始怀疑x*x会爆long long ,但是没有想到也将乘法变成加法。。太弱了；
#include<iostream> #include<cstdio> #include<time.h> #include<stdlib.h> using namespace std; typedef long long ll; int T,kase = 1,i,j,k,n,m; ll mult(ll x,ll y,ll mod) // 防止x*y爆long long; { ll ans = 0;x %= mod; while(y){ if(y&1) ans += x, y--; if(ans >= mod) ans -= mod; y >>= 1; x <<= 1; if(x >= mod) x -= mod; } return ans; } ll pow(ll a,ll n,ll mod) { a %= mod; ll ans = 1; while(n){ if(n&1) ans = mult(ans,a,mod); a = mult(a,a,mod); n >>= 1; } return ans; } bool Miller_Rabin(ll n) { if(n <= 2) return n == 2; if(n%2 == 0) return false; ll t = n - 1; while(t%2 == 0) t >>= 1; srand(time(NULL)); for(int i = 0;i < 15;i++){ ll p = rand()%(n-2)+2; if(n%p == 0) return false; ll tmp = t; ll x = pow(p,t,n); // p[i]^t % n; while(tmp < n){ ll y = mult(x,x,n); if(y == 1 && x != 1 && x != n-1) return false; x = y; tmp <<= 1; } if(x != 1) return false; // Fermat检测 } return true; } int main() { ll x; scanf("%d",&T); while(T--){ scanf("%lld",&x); puts(Miller_Rabin(x)?"Yes":"No"); } return 0; }