模板题。Pollard Rho大整数分解质因数。
以下是我的代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#define Random(n) (rand()%(n+1))
using namespace std;
typedef long long int64;
const int kMaxT(7);
int cnt,factor[107];
int64 Gcd(int64 a,int64 b)
{
for(int64 t=a%b;t;a=b,b=t,t=a%b);return abs(b);
}
int64 MutiMod(int64 a,int64 b,int64 n)
{
int64 exp(a%n),res(0);
while(b)
{
if(b&1)
{
res+=exp;
if(res>n)
res-=n;
}
exp<<=1;
if(exp>n)
exp-=n;
b>>=1;
}
return res;
}
int64 ExpMod(int64 a,int64 n,int64 b)
{
int64 r(1),t(a%b);
if(n==0) return 1%b;
while(n>1)
{
if(n&1)
r=MutiMod(r,t,b);
t=MutiMod(t,t,b);
n>>=1;
}
return MutiMod(r,t,b);
}
bool MillerRabbin(int64 n)
{
if(n==2)
return true;
if(n<2 || !(n&1))
return false;
int64 a,u(n-1),x,y;
int t(0);
while(u%2==0)
{
t++;
u>>=1;
}
srand(time(NULL));
for(int i=1;i<=kMaxT;i++)
{
a=Random(n-2)+1;
x=ExpMod(a,u,n);
for(int j=0;j<t;j++)
{
y=MutiMod(x,x,n);
if(y==1 && x!=1 && x!=n-1)
return false;
x=y;
}
if(y!=1)
return false;
}
return true;
}
int64 PollardRho(int64 n,int c)
{
int64 x(Random(n-2)+1),y(x),d,i(1),k(2);
while(true)
{
i++;
x=(MutiMod(x,x,n)+c)%n;
d=Gcd(y-x,n);
if(d>1 && d<n)
return d;
if(x==y)
return n;
if(i==k)
{
y=x;
k<<=1;
}
}
}
void FindFactor(int64 n,int k)
{
if(n==1)
return;
if(MillerRabbin(n))
{
factor[++cnt]=n;
return;
}
int64 p(n);
while(p>=n)
p=PollardRho(p,k--);
FindFactor(p,k);
FindFactor(n/p,k);
}
int main()
{
int T;
cin>>T;
while(T--)
{
int64 n;
cin>>n;
cnt=-1;
FindFactor(n,107);
if(cnt==0)
cout<<"Prime"<<endl;
else
{
int min(-1);
for(int i=0;i<=cnt;i++)
if(min<0 || min>factor[i])
min=factor[i];
cout<<min<<endl;
}
}
return 0;
}
posted on 2011-07-31 09:42
lee1r 阅读(486)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论