3667: Rabin-Miller算法
Time Limit: 60 Sec Memory Limit: 512 MBSubmit: 983 Solved: 302[][][]Description
Input
第一行：CAS,代表数据组数（不大于350），以下CAS行，每行一个数字，保证在64位长整形范围内，并且没有负数。你需要对于每个数字：第一，检验是否是质数，是质数就输出Prime
第二，如果不是质数，输出它最大的质因子是哪个。Output
第一行CAS(CAS<=350，代表测试数据的组数) 以下CAS行：每行一个数字，保证是在64位长整形范围内的正数。 对于每组测试数据：输出Prime，代表它是质数，或者输出它最大的质因子，代表它是和数
Sample Input
6 2 13 134 8897 1234567654321 1000000000000
Sample Output
Prime Prime 67 41 4649 5
HINT
数据范围：
保证cas<=350，保证所有数字均在64位长整形范围内。Source
Solution
我以为啊,这个很好
裸题,卡常..自己原来的板子被卡死了..于是换成网上的新版...
Code
#include#include #include #include #include #include using namespace std;long long read(){ long long x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}long long X,maxz;long long gcd(long long a,long long b){ if (b==0) return a; return gcd(b,a%b);}//long long mul(long long a,long long b,long long p)//{// if (b==0) return 0; if (b==1) return a%p;// long long re;// re=mul(a,b>>1,p);// if ((b&1)==1) return (re+re+a)%p;// else return (re+re)%p;//}long long mul(long long a,long long b,long long p){ long long tmp=(a*b-(long long)((long double)a/p*b+1e-8)*p); return tmp<0?tmp+p:tmp;}long long quick_pow(long long a,long long b,long long p){ long long ans=1; a%=p; for (long long i=b; i; i>>=1,a=mul(a,a,p)) if (i&1) ans=mul(ans,a,p); return ans;}bool check(long long a,long long n,long long r,long long s){ long long ans=quick_pow(a,r,n),p=ans; for(int i=1; i<=s; i++) { ans=mul(ans,ans,n); if(ans==1&&p!=1&&p!=n-1)return 1; p=ans; } if(ans!=1)return 1;else return 0;}bool Robin_Miller(long long x){ if(x<=1) return 0; if(x==2) return 1; if(x%2==0) return 0; long long r=x-1,s=0; while(r%2==0) r/=2,s++; for(int i=0; i<20; i++) if(check(rand()%(x-1)+1,x,r,s)) return 0; return 1;}long long Rho(long long x,long long t){ long long k=2,a=rand()%x,b=a,p=1; for(long long i=1; p==1; i++) { a=(mul(a,a,x)+t)%x; p=b>a?b-a:a-b; p=gcd(x,p); if(i==k) b=a,k+=k; } return p;}void work(long long x){ if(x==1) return; if(Robin_Miller(x)){maxz=max(x,maxz);return;} long long t=x; while(t==x) t=Rho(x,rand()%(x-1)+1); work(t); work(x/t);}int main(){ int n;n=read(); while (n--) { X=read(); maxz=0; work(X); if (maxz==X) puts("Prime"); else printf("%lld\n",maxz); } return 0;}
论常数的差距....:So SAD.
