//************************************************
//pollard_rho 算法进行质因数分解
//************************************************ LL factor[];//质因数分解结果（刚返回时是无序的）
int tol;////质因数的个数。数组小标从0开始 LL gcd(LL a,LL b)
{
if(a==) return ;// !!!!
if(a<) return gcd(-a,b);
while(b)
{
LL t=a%b;
a=b;
b=t;
}
return a;
} LL Pollard_rho(LL x,LL c)
{
LL i=,k=;
LL x0=rand()%x;
LL y=x0;
while()
{
i++;
x0=(mult_mod(x0,x0,x)+c)%x;
LL d=gcd(y-x0,x);
if(d!= && d!=x) return d;
if(y==x0) return x;
if(i==k) {y=x0;k+=k;}
}
} //对n进行素因子分解 void findfac(LL n)
{
if(Miller_Rabin(n))
{
factor[tol++]=n;
return;
}
LL p=n;
while(p>=n)
p=Pollard_rho(p,rand()%(n-)+);
findfac(p);
findfac(n/p);
}