[cpp]
LL mul(LL a, LL b, LL p)
{
LL rn=0, i;
for(i=1; i<=b; i<<=1,a=(a+a)%p)
if(b&i) rn=(rn+a)%p;
return rn;
} // 计算模意义下两大数乘积
LL ksm(LL a, LL b, LL p)
{
LL rn=1;
for(; b; a=mul(a,a,p),b>>=1)
if(b&1) rn=mul(rn,a,p);
return rn;
} // 计算模意义下两大数乘方
LL gcd(LL a, LL b)
{
LL tmp; if(a
while(b) tmp=a%b, a=b, b=tmp;
return a;
} // 求最大公约数
<2>Miller Robin素数测试
能在(0.25)^S的错误率下判定质数，相应地需要付出(S*log n)的时间复杂度。
原理基于两个定理：
1.若p是质数，0
2.对于0
[cpp]
bool isprime(LL n)
{
if(n==2) return true;
if(n<2 || !(n&1)) return false;
LL a,x,y, u=n-1; int t=0;
while((u&1)==0) t++, u>>=1;
for(i=0; i
{
a=rand()%(n-1)+1;
x=ksm(a,u,n);
for(int j=1; j<=t; j++)
{
y=mul(x,x,n);
if(y==1 && x!=1 && x!=n-1) return false;
x=y;
}
if(x!=1) return false;
}
return true;
}
<3>Pollcard Rho因数分解
复杂度貌似是n^(1/4)，这应该是因数分解的最快算法了。
[cpp]
void rho(LL n)
{
if(isprime(n)) { list[++top]=n; return; }
LL a,x,y,z,p;
while(true)
{
for(x=1,y=1,z=rand()+1,p=1; p==1; )
{ www.2cto.com
y = (mul(y,y,n)+z)%n;
p = gcd((x-y+n)%n,n);
x = (mul(x,x,n)+z)%n;
y = (mul(y,y,n)+z)%n;
}
if(p==n) continue;
rho(p); rho(n/p);
return;
}
}
正确性是显然的，复杂度分析么——总之很快。