传送门
这题卡的时间卡的真的厉害。不仅卡了Miller_Rabin算法，Pollard_rho算法，还卡了gcd 和 反复平方运算。
题目大意：给你一个数，如果是素数，直接输出prime,否则输出他的第一个素因子。
因为给的数特别大特别多，所以我们只能用Miller_Rabin算法进行大数判断，在判断不是素数后，还要用Pollard_rho算法进行分解。
两个都是神仙算法。首先看第一个吧，第一个算法思想简单来说就是利用费马小定理的逆，再加上二次探测后，保证了判断的准确性。
再看第二个Pollard_rho算法，Miller_Rabin算法我可以不用取随机的，但是Pollard_rho算法就是个完整的随机算法了，我感觉有点暴力，怎么说呢，有规律的暴力。
Pollard_rho 算法对于一个整数 n，首先使用 Miller_Rabin 算法判断 n 是否是素数，若 n 是素数，那么，则记录为一个素因子；如果 n 不 是素数，则按照下述方法分解 n 的一个因子 d： 先取一个随机整数 c，1≤c≤n-1；然后取另一个随机整数 x1，1≤x1≤n-1；然后计算序列 x1 x2 x3…xi xi+1…，其中，令 y=xi-1，xi 按照递归式 xi=(xi-12+c)%n 得出；每生成一项 xi 后，求 GCD(y-xi, n)，如果 GCD(y-xi, n)大于 1，那么得到一个因子 p=GCD(y-xi, n)，继续对 p 和 n/p 递归搜索，直到搜到素数为止；若 GCD(y-x, n)是 1，则重复上述操作。这样的过程一直进行 至出现了以前出现过的某个 x 为止。
#include<iostream> #include<cstdlib> #include<cstdio> #include<vector> #include<ctime> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; vector<ll> v; int testnum[]={2,3,61,5,7,11,13,19}; inline ll fmul(ll a,ll b,ll p){ //return (a%p*b%p)%p; a%=p; b%=p; ll res = 0; while(b){ if(b&1){ res+=a; res%=p; } a<<=1; if(a>=p) a%=p; b>>=1; } return res; } ll qpow(ll a,ll b,ll p){ ll res = 1; while(b){ if(b&1) res=fmul(res,a,p); a = fmul(a,a,p); b>>=1; } return res; } bool isprime(ll n){ if(n==2 || n==3) return true; if(n<2 || n%2==0) return false; ll a,d=n-1,t=0,x,y; while((d&1)==0) d>>=1,t++; for(int i=0;i<3;i++){ a = testnum[i]; x = qpow(a,d,n); for(int j=0;j<t;j++){ y = fmul(x,x,n); if(y==1 && x!=1 &&x!=n-1) return false; x=y; } if(x!=1) return false; } return true; } ll gcd(ll a,ll b){ // return b==0?a:gcd(b,a%b); if(a==0) return 1; if(a<0) return gcd(-a,b); while(b){ ll t=a%b; a=b; b=t; } return a; } ll pollard_rho(ll f,ll c){ ll i=1,k=2; ll x = rand()%f; ll y = x; while(1){ i++; x=(fmul(x,x,f)+c)%f; ll d= gcd(y-x,f); if(d!=1 && d!=x) return d; if(y==x) return f; if(i==k){ y=x; k+=k; } } } void findfac(ll n){ if(isprime(n)){ v.push_back(n); return; } ll p = n; while(p>=n) p=pollard_rho(p,rand()%(n-1)+1); findfac(p); findfac(n/p); } int main(){ int t;scanf("%d",&t); while(t--){ ll n; scanf("%lld",&n); if(isprime(n)){ printf("Prime\n"); continue; } findfac(n); ll ans = v[0]; for(int i=0;i<v.size();i++){ ans = min(ans,v[i]); } printf("%lld\n",ans); v.clear(); } return 0; }
