poj 1811 Prim test

基本上一个裸的Miller_Rabin大素数判定和一个裸的Pollard_rho素数分解算法，当模板用吧！
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<stdlib.h>
  4 #define LL long long
  5 using namespace std;
  6 const int s=20;
  7 int tol;
  8 LL factor[100];
  9 
 10 LL mult_mod(LL a,LL b,LL c)//计算a*b%c;
 11 {
 12     LL ret=0;
 13     a%=c;
 14     b%=c;
 15     while(b>0)
 16     {
 17         if(b&1) ret=(ret+a)%c;
 18         a<<=1;
 19         if(a>=c) a%=c;
 20         b>>=1;
 21     }
 22     return ret;
 23 }
 24 
 25 LL pow_mod(LL a,LL b,LL mod)//计算a^b%b
 26 {
 27     if(b==1) return a%mod;
 28     a%=mod;
 29     LL tmp=a;
 30     LL ret=1;
 31     while(b>0)
 32     {
 33         if(b&1) ret=mult_mod(ret,tmp,mod);
 34         tmp=mult_mod(tmp,tmp,mod);
 35         b>>=1;
 36     }
 37     return ret;
 38 }
 39 
 40 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
 41 //一定是合数返回true,不一定返回false
 42 bool check(LL a,LL n,LL x,LL t)
 43 {
 44     LL ret=pow_mod(a,x,n);
 45     LL last=ret;
 46     for(int i=1; i<=t; i++)
 47     {
 48         ret=mult_mod(ret,ret,n);
 49         if(ret==1&&last!=1&&last!=n-1) return 1;
 50         last=ret;
 51     }
 52     if(ret!=1) return 1;
 53     return false;
 54 }
 55 
 56 // Miller_Rabin()算法素数判定
 57 //是素数返回true.(可能是伪素数，但概率极小)
 58 //合数返回false;
 59 bool Miller_Rabin(LL a)
 60 {
 61     if(a<2) return 0;
 62     if(a==2) return 1;
 63     if((a&1==0)) return 0;
 64     LL x=a-1;
 65     LL t=0;
 66     while((x&1)==0)
 67     {
 68         x>>=1;
 69         t++;
 70     }
 71     for(int i=0; i<s; i++)
 72     {
 73         long long b=rand()%(a-1)+1;
 74         if(check(b,a,x,t))
 75             return 0;
 76     }
 77     return 1;
 78 }
 79 
 80 LL gcd(LL a,LL b)
 81 {
 82     if(a==0)return 1;
 83     if(a<0) return gcd(-a,b);
 84     while(b)
 85     {
 86         LL t=a%b;
 87         a=b;
 88         b=t;
 89     }
 90     return a;
 91 }
 92 
 93 LL Pollard_rho(LL x,LL c)
 94 {
 95     LL i=1,k=2;
 96     LL x0=rand()%x;
 97     LL y=x0;
 98     while(1)
 99     {
100         i++;
101         x0=(mult_mod(x0,x0,x)+c)%x;
102         LL d=gcd(y-x0,x);
103         if(d!=1&&d!=x) return d;
104         if(y==x0) return x;
105         if(i==k)
106         {
107             y=x0;
108             k+=k;
109         }
110     }
111 }
112 
113 void findfac(LL n)
114 {
115     if(Miller_Rabin(n))//素数
116     {
117         factor[tol++]=n;
118         return;
119     }
120     LL p=n;
121     while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1);
122     findfac(p);
123     findfac(n/p);
124 }
125 
126 int main()
127 {
128     LL a;
129     int n;
130     scanf("%d",&n);
131     while(n--)
132     {
133         scanf("%lld",&a);
134         if(Miller_Rabin(a))
135         {
136             puts("Prime");
137             continue;
138         }
139         tol=0;
140         findfac(a);
141         LL ans=factor[0];
142         for(int i=1;i<tol;i++)
143           if(factor[i]<ans)
144              ans=factor[i];
145         printf("%lld
",ans);
146     }
147     return 0;
148 }
View Code