Pollard rho算法+Miller Rabin算法 BZOJ 3668 Rabin-Miller算法

BZOJ 3667: Rabin-Miller算法

Time Limit: 60 Sec Memory Limit: 512 MB
Submit: 1044 Solved: 322
[Submit][Status][Discuss]

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位长整形范围内。

分析：虽然题目叫做Miller rabin算法，不过真正上也需要Pollard rho算法

 /*貌似这个代码在BZOJ上的评测器就会运行错误，但是在POJ上一道原题却通过了（POJ上语言选C++可以过，选择G++就过不了）*/

 #include<iostream>

 using namespace std;

 #include<cstdio>

 #define S 10

 #include<cstdlib>

 #include<ctime>

 #define ll long long

 ll cas, maxz=-;

 ll read()

 {

     ll ans=;char c;

     c=getchar();

     while(c<''||c>'') c=getchar();

     while(c>=''&&c<='')

     {

         ans=ans*+c-'';

         c=getchar();

     }

     return ans;

 }

 ll quick_mul_mod(ll a,ll b,ll c)//a*b%c

 {

     ll ret=;

     a%=c;b%=c;

     while(b)

     {

         if(b&)

         {

             ret+=a;

             ret%=c;

             b--;

         }

         a<<=;

         a%=c;

         b>>=;

     }

     return ret;

 }

 ll gcd(ll a,ll b)

 {

     if(a==) return ;

     if(a<) return gcd(-a,b);

     if(b==)

     return a;

     return gcd(b,a%b);

 }

 ll Pollard_rho(ll x,ll c)

 {

     ll x1=rand()%(x-)+;

     ll x2=x1;

     int i=,k=;

     while()

     {

         i++;

         x1=(quick_mul_mod(x1,x1,x)+c)%x;

         ll d=gcd(x2-x1,x);

         if(d!=&&d!=x) return d;

         if(x2==x1) return x;

         if(i==k)

         {

             x2=x1;

             k+=k;

         }

     }

 }

 ll quick_mod(ll a,ll b,ll c)//ji suan a^b%c

 {

     ll ans=;

     a%=c;

     while(b)

     {

         if(b&)

         {

             b--;

             ans=quick_mul_mod(ans,a,c);

         }

         b>>=;

         a=quick_mul_mod(a,a,c);

     }

     return ans;

 }

 bool Miller_rabin(ll n)

 {

     if(n==) return true;

     if(n<=||!(n&)) return false;

     ll u=n-,t=;

     while(!(u&))

     {

         u>>=;

         t++;

     }

     for(int i=;i<S;++i)

     {

         ll x=rand()%(n-)+;

         x=quick_mod(x,u,n);

         for(int i=;i<=t;++i)

         {

             ll y=quick_mul_mod(x,x,n);

             if(y==&&x!=&&x!=n-)

               return false;

             x=y;

         }

         if(x!=) return false;

     }

     return true;

 }

 void findpri(ll n)

 {

     if(n==) return;

     if(Miller_rabin(n))

     {

         maxz=max(maxz,n);

         return;

     }

     ll p=n;

     while(p==n)

       p=Pollard_rho(p,rand()%(n-)+);

     findpri(p);

     findpri(n/p);

 }

 int main()

 {

     srand(time());

     cas=read();

     while(cas--)

     {

         maxz=;

         ll n=read();

         findpri(n);

         if(maxz==n)/*最大的质因数就是本身*/

           printf("Prime\n");

         else printf("%lld\n",maxz);

     }

     return ;

  }

秒客网