PoRho模板

以O(n^(1/4))的复杂度对一个数进行质因子分解

无敌了已经

ll ksc(int a,int b,int p){ll z = (long double)a/p*b;ll res =(ull)a*b -(ull)(z*p);return (res+p)%p;
}
int ksm(int a,int b,int p){int res=1;while(b){if(b&1)res=ksc(res,a,p);a=ksc(a,a,p);b>>=1;}return res%p;
}
int mr(int a,int p){if(ksm(a,p-1,p)!=1)return 0;int x= p-1,y=0;while(x%2==0){x>>=1;y=ksm(a,x,p);if(y!=1&&y!=p-1)return 0;if(y==p-1)return 1;}return 1;
}
int isprime(int x){if(x<2)return 0;if(x==2||x==3||x==5||x==7||x==43)return 1;return mr(2,x)&&mr(3,x)&&mr(5,x)&&mr(7,x)&&mr(43,x);
}
int rho(int n){ll x,y,z,c,g;ll i,j;//f(x) =x*x + c//gcd(abs(y-x),n)>1 => 找到非平凡因子while(1){x=y=rand()%n;z=1;c=rand()%n;i=0;j=1;while(++i){x=(ksc(x,x,n)+c)%n;z=ksc(z,abs(y-x),n);if(x==y||!z)break;if(!(i%127)||i==j){g=__gcd(z,n);if(g>1)return g;if(i==j)y=x,j<<=1;}}}
}
vector<int>v;
void work(int n){if(n==1)return;if(isprime(n)){v.pb(n);return;}int pi = rho(n);while(n%pi==0)n/=pi;work(pi);work(n);
}