擴展歐幾裡得
求二元一次不定式方程 的一組解。
int exgcd(int a,int b,int &x,int &y) { int t; if(!b) {x=1;y=0;return a;} t=exgcd(b,a%b,y,x); y-=(a/b)*x; return t; }
線性篩質數
維護一個質數表。對於每個數 , 從小到大枚舉所有質數 ,將 打上標記。 如果 , 停止枚舉。
void getprime() { int i,j; for(i=2;i<=n;i++) { if(!b[i]) prime[++tot]=i; for(j=1;j<=tot&&i*prime[j]<=n;j++) { b[i*prime[j]]=true; if(!i%prime[j]) break; } } }
線性求逆元
逆元的定義:稱x是a在模b意義下的逆元,可理解為。
給定一個質數 ,求出 至 的逆元。
證明:
費馬小定理
若 是質數, 則
證明:
因為 , 所以.
線性求歐拉函數
歐拉函數的定義:小於等於的正整數中與互質的數的個數。
設 為 最小的質數,。在線性篩中,被篩掉。
當時,。
當時,。
void getphi() { int i,j; phi[1]=1; for(i=2;i<=n;i++) { if(!b[i]) { prime[++tot]=i; phi[i]=i-1; } for(j=1;j<=tot;j++) { if(i*prime[j]>n) break; b[i*prime[j]]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } }
歐拉定理
若 , 則 。
證明:
記 , 記 為 到 中與 互質的數。
由 消去律 得
Miller-Rabin算法 素數測試
記
在 中隨機選取一個整數 , 如果 或 , 那麼我們認為n是質數。
錯誤率不超過1/4,重復若干次即可。
long long mod_mul(long long,long long,long long); long long mod_exp(long long,long long,long long); bool miller_rabbin(long long n) { int i,j,t; long long a,x,y,u; if(n==2)return true; if(n<2||!(n&1)) return false; t=0;u=n-1; while((u&1)==0) t++,u>>=1; for(i=1;i<=tim;i++) { a=rand()%(n-1)+1; x=mod_exp(a,u,n); for(j=0;j<t;j++) { y=mod_mul(x,x,n); if(y==1&&x!=1&&x!=n-1) return false; x=y; } if(x!=1) return false; } return true; } long long mod_mul(long long a,long long b,long long mod) { long long res=0; while(b) { if(b&1) res=(res+a)%mod; a=(a+a)%mod; b>>=1; } return res; } long long mod_exp(long long a,long long b,long long mod) { long long res=1; while(b) { if(b&1) res=mod_mul(res,a,mod); a=mod_mul(a,a,mod); b>>=1; } return res; }
Pollard-rho算法 分解合數
中國剩余定理
解方程組 其中 兩兩互質。
大步小步法(BSGS)及其拓展
求最小的 使得 , 為質數。
莫比烏斯反演
已知 求 。
原根的基本性質
拉格朗日定理
二次剩余