1 //************************************************ 2 //pollard_rho 算法进行质因数分解 3 //************************************************ 4  5 LL factor[100];//质因数分解结果（刚返回时是无序的） 6 int tol;////质因数的个数。数组小标从0开始 7  8 LL gcd(LL a,LL b) 9 {10     if(a==0) return 1;//  !!!!11     if(a<0)  return gcd(-a,b);12     while(b)13     {14         LL t=a%b;15         a=b;16         b=t;17     }18     return a;19 }20 21 LL Pollard_rho(LL x,LL c)22 {23     LL i=1,k=2;24     LL x0=rand()%x;25     LL y=x0;26     while(1)27     {28         i++;29         x0=(mult_mod(x0,x0,x)+c)%x;30         LL d=gcd(y-x0,x);31         if(d!=1 && d!=x) return d;32         if(y==x0) return x;33         if(i==k) {y=x0;k+=k;}34     }35 }36 37 //对n进行素因子分解38 39 void findfac(LL n)40 {41     if(Miller_Rabin(n))42     {43         factor[tol++]=n;44         return;45     }46     LL p=n;47     while(p>=n)48     p=Pollard_rho(p,rand()%(n-1)+1);49     findfac(p);50     findfac(n/p);51 }