復習筆記——數論

數論復習筆記

素數

線性篩

每個合數被最小質因子篩掉
用線性篩可求 \(phi\) 、\(mu\) 等積性函數

int p[N],prime[N],pnum;
void getp(){
    for(int i=2;i<N;i++) p[i]=1;
    for(int i=2;i<N;i++){
        if(p[i]) prime[pnum++]=i;
        for(int j=0;j<pnum && 1ll*i*prime[j]<N;j++){
            p[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}

試除法判斷素數

用2~ \(\sqrt{n}\) 試除

bool isprime(int x){
    for(int i=2;i*i<=x;i++)
        if(x%i==0) return false;
    return true;
}

Miller-Rabin素性測試

Pollard-Rho分解質因數

最大公約數

最大公約數與最小公倍數

輾轉相除法

int gcd(int a,int b) { return b?gcd(b,a%b):a; }

\(lcm(a,b)=\frac{ab}{gcd(a,b)}\)

翡蜀定理

若 \(a,b\) 為整數，\(gcd(a,b)=d\)，則對任意整數 \(x,y\) ，\(ax+by=z\)，\(d|z\)
存在不止一組 \(x,y\) 使 \(ax+by=d\)

擴展歐拉定理

用來求一組 \(x,y\) 滿足 \(ax+by=gcd(a,b)\)

推導：
要求 \(ax+by=gcd(a,b)=gcd(b,a%b)\)
假設已求出 \(by'+(a-(a/b)b)x'=gcd(b,a%b)\)
則 \(x=x',y=y'-(a/b)x'\)

int extgcd(int a,int b,int &x,int &y) { //return gcd
    if(b==0) { x=1; y=0; return a; }
    int z=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return z;
}

若已求出一組解 \(x_0,y_0\)
則任意解滿足 \(x=x_0+k\times \frac{b}{gcd(a,b)},y=y_0-k\times \frac{a}{gcd(a,b)}\)

費馬小定理

若 \(p\) 為素數，\(gcd(a,p)=1\) ，則 \(a^{p-1} \equiv 1(mod\ p)\)
也即對任意整數 \(a\) ，\(a^p \equiv a(mod\ p)\)

證明

構造 \(p\) 的完全剩余系 \(A=\{0,1,2,\dots ,p-1 \}\)
取滿足 \(gcd(a,p)=1\) 的數 \(a\) ，則 \(B=\{0a,a,2a,\dots,(p-1)a \}\) 也為 \(p\) 的完全剩余系
（可以反證，若有兩個數模 \(p\) 同余，即 \(ai\equiv aj(mod\ p)\)，則 \(ai-aj\equiv a(i-j) \equiv i-j \equiv 0 (mod\ p)\)，則 \(i,j\) 相等）

去掉0，則 \(1\times 2\times \dots \times (p-1) \equiv a\times 2a\times \dots \times (p-1)a \ \ \ (mod\ p)\)
即 \(1\equiv a^{p-1} (mod\ p)\)

歐拉定理

歐拉函數

\(\phi(n)\) 表示 1~ \(n\) 中與 \(n\) 互質（\(gcd(i,n)=1\)）的數的個數
設 \(n\) 的質因子為 \(p_1,p_2,\dots ,p_m\)
則 \(\phi(n)=n\prod\limits_{i=1}^m \frac{p_i-1}{p_i}\)

一些性質：

\(\phi(1)=1\)
若 \(n\) 為質數，則 \(\phi(n)=n-1\)
積性函數——若 \(m,n\) 互質，則 \(\phi(nm)=\phi(n)\phi(m)\)
小于 \(n\) 且與 \(n\) 互質的數之和為 \(\frac{n\phi(n)}{2}\) (\(n>1\))

用線性篩求。

int phi[N],prime[N],pnum;
int getphi(){
    phi[1]=1;
    for(int i=2;i<N;i++) phi[i]=i-1;
    for(int i=2;i<N;i++){
        if(phi[i]==i-1) prime[pnum++]=i;
        for(int j=0;j<pnum && 1ll*i*prime[j]<N;j++){
            if(i%prime[j]==0) {
                phi[prime[j]*i]=phi[i]*prime[j];
                break;
            }
            phi[prime[j]*i]=phi[i]*(prime[j]-1);
        }
    }
}

求一個數的歐拉函數，要先分解質因數

int tot,fac[N];
void get_prime(int x){
    int y=x;    
    tot=0;
    for(int i=2;i*i<=y;i++){
        if(y%i) continue;
        fac[++tot]=i;
        while(y%i==0) y/=i;
    }
    if(y!=1) fac[++tot]=y;
}
int phi(int x){
    int ret=x;
    get_prime(x);
    for(int i=1;i<=tot;i++) ret=ret/fac[i]*(fac[i]-1);
    return ret;
}

歐拉定理

對任意數 \(p\) ，若 \(gcd(a,p)=1\)，則 \(a^{\phi(p)}\equiv 1(mod\ p)\)

證明：
取縮系 \(A=\{r_1,r_2,\dots,r_{\phi(p)}\}\)
則 \(B=\{ar_1,ar_2,\dots,ar_{\phi(p)}\}\) 也為縮系
（反證：若\(ar_i\equiv ar_j(mod\ p)\)，則 \(ar_i-ar_j\equiv a(r_i-r_j) \equiv r_i-r_j \equiv 0 (mod\ p)\)，則 \(r_i,r_j\) 相等）
還是都乘起來就得到 \(a^{\phi(p)}\equiv 1(mod\ p)\)

可以發現費馬小定理是歐拉定理的特殊情況。

擴展歐拉定理

\( \begin{equation} a^b\equiv \begin{cases} a^{b\% \phi(p)}& gcd(a,p)=1\\ a^b& b<\phi(p)\\ a^{b\% \phi(p)+\phi(p)}& gcd(a,p) \neq 1,b\geq \phi(p) \end{cases} \ \ (mod\ p) \end{equation} \)
并不會證……

威爾遜定理

當且僅當 \(p\) 為素數時，\((p-1)!\equiv p-1 \equiv -1(mod \ p)\)

逆元

定義（我自己說的）：當 \(gcd(a,p)=1\) 時，滿足 \(a\times b \equiv 1(mod\ p)\) 的小于 \(p\) 的數 \(b\) 為 \(a\) 對 \(p\) 的逆元

求法：

\(p\) 為質數：費馬小定理 \(a^{p-2}\equiv \frac{1}{a} (mod\ p)\)
\(p\) 不是素數：歐拉定理 \(a^{\phi(p)-1} \equiv \frac{1}{a} (mod\ p)\)
擴展歐幾里得：\(ax\equiv 1 (mod\ p) \Rightarrow ax+py=1\)
線性篩1~ \(n\) 的逆元： \(inv[1]=1,\ inv[i]=p-(p/i)\times inv[p\%i] \% p\)

階與原根

階

若 \(gcd(a,p)=1\) ，定義滿足 \(a^l\equiv 1(mod\ p)\) 的最小的 \(l\) 稱為 \(a\) 模 \(p\) 的階。
記為 \(ord_p a\)

一些性質：

對任意使 \(a^l \equiv 1 (mod\ p)\) 的 \(l\) ，有 \(ord_p a |l\)。由歐拉定理，\(ord_p a| \phi(p)\)
\(1,a,a^2,\dots,a^{ord_pa-1}\) 關于模 \(p\) 互不同余
若 \(ord_pa=l\)，則 \(ord_p a^t=\frac{l}{gcd(t,l)}\)
\(a^i\equiv a^j(mod\ p)\) 當且僅當 \(i\equiv j(mod\ ord_pa)\)

原根

若 \(gcd(g,p)=1\) 且 \(ord_pg=\phi(p)\)，則稱 \(g\) 為模 \(p\) 的原根。

一些性質：

若 \(g\) 為模 \(p\) 的原根，則 \(A={g,g^2,\dots,g^{\phi(p)}}\) 構成 \(p\) 的既約剩余系
有原根的數：1,2,4,\(p^a\),\(2p^a\) 其中 \(p\) 為奇素數，\(a\) 為正整數
判定原根：設 \(p_1,p_2,\dots,p_m\) 是 \(\phi(n)\) 的所有質因數，則 \(g\) 是模 \(n\) 的原根當且僅當對任意 \(1\leq i \leq m\) ，有 \(g^{\frac{\phi(n)}{p_i}} \ne 1 (mod\ n)\) （找不到不同余號所以用的不等于號）
若 \(p\) 有原根，則 \(p\) 的原根有 \(\phi(\phi(p))\) 個（證明：設 \(g\) 為一個原根，則 \(g^t\) 為原根當且僅當 \(\frac{\phi(p)}{gcd(\phi(p),t)}=\phi(p)\)，所以共 \(\phi(\phi(p))\) 個）
\(p\) 的最小原根在 \(O(p^{0.25})\) 級別，可暴力求

小技巧：利用原根 \(g\) 可將一個與 \(p\) 互質的數表示為 \(g^t\)，指標 \(t\) 可方便一些運算或幫助發現性質。

bool check(int x,int p){ //判斷x是否為模p原根
    int q=Phi(p); //phi(p) 的質因子在 fac[]中，共tot個
    for(int i=1;i<=tot;i++)
        if(Pow_mod(x,q/fac[i],p)==1) return false;
    return true;
}
int getg(int p){ //求最小原根，若無原根則返回0
    if(p==1 || p==2) return 1;
    if(p==4) return 3;

    //判斷有
    int q=p,r;
    if(p%2==0) q/=2;
    for(int i=2;i*i<=q;i++)
         if(q%i==0) { r=i; break; }
    if(!isprime(r)) return 0;
    while(q%r==0) q/=r;
    if(q!=1) return 0;

    for(int i=2;i<p;i++)
        if(gcd(i,p)==1 && check(i,p)) return i;
}
int get_all_g(int p){ //求所有原根，存入 A[]，返回原根數量
    int g=getg(p),z=Phi(p);
    if(!g) return 0;
    int ret=0; A[++ret]=g;
    for(int i=2;i<=z;i++) if(gcd(i,z)==1) A[++ret]=Pow_mod(g,i,p);
    return ret;
}

BSGS

給定 \(a,b,p\)，\(gcd(a,p)=1\)，\(p\) 為質數，求最小非負整數 \(x\) 滿足 \(a^x\equiv b(mod\ p)\)

由于 \(p\) 為質數，所以若有解，則最小非負整數解一定滿足 \(x\leq p-1\)
分塊，將 \(a^x\) 寫成 \(a^{im-j}\)，其中 \(m=\lceil \sqrt{p}\rceil,0\leq i,j\leq \lceil \sqrt{p} \rceil\)
則 \((a^m)^i \times a^{-j} \equiv b(mod\ p) \Rightarrow (a^m)^i\equiv b\times a^j(mod\ p)\)
存下來所有 \(ba^j\) ，然后從小到大枚舉 \(i\) ，判斷是否有與 \((a^m)^i\) 相等的 \(ba^j\)

不要用 \(map\) ，要用哈希表存……
注意可能無解！！！

vector<Pr> hs[4987657];
int Hash(int x) { return (1ll*x*x%4987657+x%100007)%4987657; }
void ins(Pr x){
	int id=Hash(x.fi);
	hs[id].pb(x);
}
int has(int x){
	int id=Hash(x);
	for(int i=0;i<hs[id].size();i++)
		if(hs[id][i].fi==x) return hs[id][i].se;
	return -1;
}
int BSGS(int a,int b,int p){
	int m=ceil(sqrt(p)),q=Pow_mod(a,m,p); //a^(im-j)=b(mod p)
	for(int i=0,cur=1;i<=m;i++){
		ins(Pr(1ll*cur*b%p,i));
		cur=1ll*cur*a%p;
	}
	for(int i=1,cur=q;i<=m;i++){
		int t=has(cur);
		if(t!=-1) return i*m-t;
		cur=1ll*cur*q%p;
	}
	return -1;
}

擴展BSGS

給定 \(a,b,p\)，\(gcd(a,p)=1\)，\(p\) 不一定為質數，求最小非負整數 \(x\) 滿足 \(a^x\equiv b(mod\ p)\)

如果 \(gcd(a,p)=1\) ，那么 \(x<p\) ，仍可用 \(BSGS\) 求解。
否則，設 \(d=gcd(a,p)\)
若 \(d\nmid b\) 則無解
否則寫成 \(\frac{a}w0obha2h00 \times a^{x-1} \equiv \frac{b}w0obha2h00 (mod\ \frac{p}w0obha2h00)\)
由于此時 \(gcd(\frac{a}w0obha2h00,\frac{p}w0obha2h00)=1\)，所以可以把 \(\frac{a}w0obha2h00\) 除到另一邊
得到 \(a^{x-1} \equiv \frac{b/d}{a/d} (mod/ p/d)\) 子問題遞歸求解即可。
注意若某次 \(b=1\) ，則可直接返回0，不用再往下遞歸了

unordered_map<int,int> mp;
int BSGS(int a,int b,int p){
	if(b==1) return 0;//!!!
	int m=ceil(sqrt(p)),q=Pow_mod(a,m,p);
	mp.clear();
	for(int i=0,cur=b;i<=m;i++) mp[cur]=i,cur=1ll*cur*a%p;
	for(int i=1,cur=q;i<=m;i++){
		if(mp[cur] || cur==b) return i*m-mp[cur];
		cur=1ll*cur*q%p;
	}
	return -1;
}
int extBSGS(int a,int b,int p){
	int z=gcd(a,p),bb=b,pp=p,k=0;
	while(z>1 && b!=1){ //a^(x-k)=bb(mod pp)
		if(bb%z!=0) return -1;
		//a/d * a^(x-k-1)=bb/d (mod pp/d)
		bb/=z; pp/=z;
		bb=1ll*bb*inv(a/z,pp)%pp;
		z=gcd(a,pp); k++;
	}
	
	int ret=BSGS(a,bb,pp);
	if(ret==-1) return -1;
	ret+=k;
	for(int i=k-1;i>=0;i--) if(Pow_mod(a,i,p)==b) ret=i;
	return ret; 
}

同余方程

一次同余方程

形如 \(a_1x_1+a_2x_2+\dots+a_nx_n \equiv b(mod\ m)\) 的方程

有解的充要條件是 \(gcd(a_1,a_2,\dots,a_n,m)|b\) ，在模 \(m\) 意義下共 \(m^{n-1}\times gcd(a_1,a_2,\dots,a_n,m)\) 個解

中國剩余定理

設正整數 \(m_1,m_2,\dots,m_n\) 兩兩互質
求解同余方程組 \(x\equiv a_i(mod\ m_i)\)

在模 \(M=\prod m_i\) 下有唯一解 \(\sum\limits_{i=1}^n \frac{M}{m_i} \times a_i\cdot inv(\frac{M}{m_i},m_i)\)

ll m[N],a[N];
int n;
ll crt(){
	ll M=1;
	for(int i=1;i<=n;i++) M=M*m[i];
	ll ret=0;
	for(int i=1;i<=n;i++){
		ll mm=M/m[i];
		ret=(ret+(inv(mm,m[i])*a[i])%m[i]*mm%M)%M; //注意有的地方模 m[i]
	} 
	return ret;
}

擴展中國剩余定理

模數 \(m_1,m_2,\dots,m_n\) 不一定互質

考慮合并兩個方程 \(x\equiv a_1(mod\ m_1),x\equiv a_2(mod\ m_2)\)
可寫成 \(x=pm_1+a_1=qm_2+a_2\)
則 \(pm_1-qm_2=a_2-a_1\)
若 \(gcd(m_1,m_2) \nmid (a_2-a_1)\) 則無解
否則求出一組滿足條件的 \((p_0,q_0)\)，對應的 \(x=p_0m_1+a_1\)；而該方程組所有解為 \(p=p_0+k\frac{m_2}{gcd(m_1,m_2)},q=q_0-k\frac{m_1}{gcd(m_1,m_2)}\)，所以對應的所有 \(x=(p_0+k\frac{m_2}{gcd(m_1,m_2)})m_1+a_1=k\times (\frac{m_1m_2}{gcd(m_1,m_2)})+p_0m_1+a_1\)
方程轉化為 \(x\equiv p_0m_1+a_1 (mod\ \frac{m_1m_2}{gcd(m_1,m_2)})\)

int n;
ll a[N],m[N];
ll extcrt(){
	ll aa=a[1],mm=m[1];
	for(int i=2;i<=n;i++){
		ll x,y,z=extgcd(mm,m[i],x,y);
		ll q=m[i]/z;
		if(abs(aa-a[i])%z) return -1;
		x=mul(x,(a[i]-aa)/z,q);
		q=q*mm;
		aa=x*mm+aa; mm=q;
	}
	return aa;
}

組合數取模

計算 \(C_m^n \% p\)

\(1\leq m \leq 10^3\) 楊輝三角
\(1 \leq m \leq 10^6\)，\(p\) 為質數：預處理 \(mul[],inv[]\)
\(1\leq m\leq 10^6\) ，\(p\)為較小合數：暴力分解質因數
\(1\leq m\leq 10^{18} ,1\leq p \leq 10^5\) ，\(p\) 為質數：lucas定理
\(1\leq m \leq 10^{18}\) ，\(p\) 不是質數：擴展lucas定理

lucas定理

對于質數 \(p\) ，\(\binom{n}{m} mod\ p=\binom{n/p}{m/p}\times \binom{n\ mod\ p}{m\ mod\ p} mod\ p\)

ll C(int x,int y){ //x>y
	if(y>x) return 0;
	return (fac[x]*Pow_mod((fac[y]*fac[x-y])%P,P-2))%P;
}
ll lucas(int x,int y){
	if(y==0) return 1;
	return (C(x%P,y%P)*lucas(x/P,y/P))%P;
}

擴展lucas定理

N次剩余

二次剩余

N次剩余

posted @ 2020-08-08 13:09 秋千旁的蜂蝶~ 閱讀(175) 評論(0) 收藏舉報

刷新頁面返回頂部

秋千旁的蜂蝶~

盡管走下去，不必逗留著，采鮮花來保存，因為這一路上，花自然繼續開放~

復習筆記——數論

素數

線性篩

試除法判斷素數

Miller-Rabin素性測試

Pollard-Rho分解質因數

最大公約數

最大公約數與最小公倍數

翡蜀定理

擴展歐拉定理

費馬小定理

費馬小定理

證明

歐拉定理

歐拉函數

歐拉定理

擴展歐拉定理

威爾遜定理

逆元

階與原根

階

原根

BSGS

BSGS

擴展BSGS

同余方程

一次同余方程

中國剩余定理

擴展中國剩余定理

組合數取模

lucas定理

擴展lucas定理

N次剩余

二次剩余

N次剩余

公告