<1>預備算法 [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<b) tmp=a,a=b,b=tmp; while(b) tmp=a%b, a=b, b=tmp; return a; } // 求最大公約數 <2>Miller Robin素數測試 能在(0.25)^S的錯誤率下判定質數，相應地需要付出(S*log n)的時間復雜度。 原理基於兩個定理： 1.若p是質數，0<a<p，那麼a^(p-1)≡1(mod p)。 2.對於0<x<p，x^2≡1(mod p) 有且只有兩解： x=1和x=p-1。 [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<S; 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; } } 正確性是顯然的，復雜度分析麼——總之很快。
