【數論】ACM數論知識總結

待更新……

數論是數學的一個分支，研究的是整數的性質，本篇文章總結的是數論在ACM中的常見應用，

一.質數

1.定義

質數，又稱素數，若一個正整數無法被除了1和它自身以外的其它數整除，則稱其為質數，否則為合數，特殊地，1既不是合數也不是質數

2.質數的判斷

給定一個數，判斷是否為質數的方法：

試除法： 檢查所有可能成為n的因子的數，若沒有找到因子，則證明這個數是一個質數

一種樸素的做法就是從2遍歷到N-1觀察有無N的因子，若沒有則說明N為質數，依據的想法是N的因子必然在1~N的范圍內

改進： 其實我們只要找到一個N的因子（除了1和它本身）就可以證明N是個合數，

定理：如果N是一個合數，則必然存在一個N的因子T，滿足 2 ≤ T ≤ √ N 2≤T≤√N 2≤T≤√N

證明：反證法即可，假設合數N的所有因子都大于 √ N √N √N，則任取一因子X，因為X為N的因子，所以N/X也是N的一個因子，而由于X大于 √ N √N √N，所以N/X必然小于 √ N √N √N，與假設相矛盾

根據這個定理，我們只需要從2遍歷到√N即可，時間復雜度縮小為 O （ √ N ） O（√N） O（√N），若沒找到因子則N為質數，

其它的想法：

素數篩進行預處理，用prime陣列存放所有素數，然后從 p r i m e [ 1 ] prime[1] prime[1]遍歷到 p r i m e [ i ] ? p r i m e [ i ] ≤ N prime[i]*prime[i]≤N prime[i]?prime[i]≤N，因為N如果是合數，則必然存在小于等于√N的素數因子

證明：前文已經證明過必然存在小于等于√N的因子，如果這個因子是素數自不必說，如果是合數，那么合數可以被分解為素因子的乘積，

目的：可以進一步減少時間復雜度，需要遍歷的數更少了（因為素數的分布相對稀疏，10萬以內的素數只有9500多個）

當然這只是我個人的想法，沒有仔細的驗證與思考，并且大部分時候O（√N）的復雜度就已經很優秀了

3.質數的篩選

篩選：即從1~N中篩選出所有的質數

思路：一個數x的倍數——2x,3x,4x……必然不是素數

具體做法：從2開始掃描所有的數x，并將x的所有倍數標記為合數，如果掃描到一個數y，發現y沒被標記過，說明y一定是素數，因為2~y-1沒有y的因子，符合素數定義

因為每個合數必然有質因子，所以只讓素數來進行標記的作業以減少重復標記，比如27讓3來標記為合數即可，

這就是埃氏篩

缺點：有些數仍會被重復標記，比如12既是3的倍數又是2的倍數，具有多個質因子的數會被重復標記

改進：

線性篩/歐拉篩：

即找到一個數的唯一產生方式：讓一個數的最小質因子對其進行標記，比如12，雖然有2，3兩個質因子，但只讓2來標記12，

時間復雜度接近 O ( N ) O(N) O(N)，所以稱為線性篩

實作：

int Prime[100005];    //存放所有的質數
bool Isprime[100005]; //判斷一個數是否為質數
int cnt=1;

void get_Prime(){
  for(int i=2;i<=100000;i++) Isprime[i]=1; //先默認所有數為質數
  for(int i=2;i<=100000;i++){
    if(Isprime[i]) Prime[cnt++]=i;
    for(int j=1;j<cnt&&Prime[j]*i<=100000;j++){ 
        Isprime[Prime[j]*i]=0; //將其標記為合數
        if(i%Prime[j]==0)
            break;
    }
  }
}

對于if(i%Prime[j]==0) break; 的解釋：

線性篩的思想是只讓最小質因子對合數進行標記，也就是：Isprime[Prime[j]*i]=0; 這句話，這里Prime[j]即最小質因子，

如果i%Prime[j]==0 ，不妨將i表示為k*Prime[j]，如果令j++繼續篩下去的話，下一個要篩的數是Prime[j+1]*i，顯然這個數的最小質因子應該是Prime[j]而不是Prime[j+1]，違背了線性篩的思想，所以需要break

4.質因子分解

算識訓本定理：

任何一個大于1的正整數都可以被分解為質因子的冪次的積

即 N = P 1 a 1 ? P 2 a 2 ? P 3 a 3 ? ? ? P m a m N=P_1^{a_1}\cdot P_2^{a_2}\cdot P_3^{a_3}\cdot\cdot\cdot P_m^{a_m} N=P1a1???P2a2???P3a3?????Pmam??

這個定理看似非常簡單，但是在很多地方都會應用到，要有將一個數分解為質因子冪次乘積的思想

分解質因子：

int factor[100];
int cnt=0;

void divide(int N){
    cnt=0;
    for(int i=2;i*i<=N;i++){
       if(N%i==0){
         factor[cnt++]=i;
         while(N%i==0)
            N/=i;
       }
    }
    if(N>1)  factor[cnt++]=N; //質數在根號N內沒有因子，故可能沒除完
}

如果還想知道每個質因子的冪次再用一個陣列存就行

5.互質

最大公約數：great common divisor，簡稱gcd，兩個數的最大公約數即兩個數共有的約數（因子）中值最大的數，

互質定義：若gcd(a,b)=1，則稱a與b互質，（即不含共同因子）

常見的求gcd的方法為歐幾里得演算法，時間復雜度為 O ( l o g ( N ) ) O(log(N)) O(log(N))的級別

關于歐幾里得演算法求gcd的證明：歐幾里得演算法證明

歐拉函式：

在數論中，對正整數n，歐拉函式是小于或等于n的正整數中與n互質的數的數目（因此φ(1)=1），此函式以其首名研究者歐拉命名(Euler’s totient function)，它又稱為Euler’s totient function、φ函式、歐拉商數等， 例如φ(8)=4，因為1,3,5,7均和8互質，

具體資訊可見：歐拉函式計算及打表

二.同余

1.模運算

對于任意的兩個整數a、b(b>0)，必然存在等式：

a = k b + r a=kb+r a=kb+r

其中k為a除以b的商，r為a除以b的余數，在C語言中，可以利用a/b得到k，利用a%b得到r，前者稱為整除，后者即模運算，

模運算的實質其實就是a-kb

性質：

① ( a + b ) % p = ( a % p + b % p ) % p (a+b)\%p=(a\%p+b\%p)\%p (a+b)%p=(a%p+b%p)%p

② ( a ? b ) % p = ( a % p ? b % p + p ) % p (a-b)\%p=(a\%p-b\%p+p)\%p (a?b)%p=(a%p?b%p+p)%p（加p防止結果變為負數）

③ ( a ? b ) % p = ( a % p ) ? ( b % p ) % p (a*b)\%p=(a\%p)*(b\%p)\%p (a?b)%p=(a%p)?(b%p)%p

④除法不滿足分配律，需要用到乘法逆元將除法轉化為乘法：

乘法逆元：

若 b ? b ? 1 ≡ 1 （ m o d p ) b\cdot b^{-1} ≡ 1（mod\ p) b?b?1≡1（mod p)

則稱 b ? 1 b^{-1} b?1為b在模p下的乘法逆元，可以理解為模p意義下的倒數

則 ( a / b ) % p = a ? b ? 1 % p (a/b)\%p=a*b^{-1}\%p (a/b)%p=a?b?1%p 將除法轉化為了乘法

乘法逆元存在的前提是 g c d ( b , p ) = 1 gcd(b,p)=1 gcd(b,p)=1

在ACM中用到的模數p一般都是質數，所以只要b不為0或p的倍數即可，

若p不是質數，則要求b、p互質

逆元求法：

一個數在模p意義下的乘法逆元有很多種求法，這里寫一下我常用的一種求逆元的方法：

費馬小定理：

p為質數且gcd(b,p)=1，則 b p ? 1 ≡ 1 （ m o d p ) b^{p-1}≡ 1（mod\ p) bp?1≡1（mod p)

也就是說 b p ? 1 % p = 1 b^{p-1}\%p=1 bp?1%p=1

可以驗證一下：

當p=3時， 2 2 , 4 2 , 5 2 , 7 2 2^2,4^2,5^2,7^2 22,42,52,72模p都等于1

而 b p ? 1 = b p ? 2 ? b b^{p-1}=b^{p-2}\cdot b bp?1=bp?2?b

所以b的一個乘法逆元為 b p ? 2 b^{p-2} bp?2，用快速冪即可較快求得

long long inv(long long x){
   return quickpow(x,mod-2)%mod;
}

⑤快速乘法

C自帶的乘法運算很優秀，但是在計算 a ? b % p a\cdot b \%p a?b%p時，如果p很大，即使使用分配律還是可能會超過資料型別上限，所以可以使用快速乘法來避免這個問題，不會快速乘的可以看這篇↓：

快速冪+快速乘法

2.定義

若整數a和整數b除以正整數m的余數相等(即 a % m = b % m a\% m=b\%m a%m=b%m)，則稱a，b模m同余，記為 a ≡ b ( m o d m ) a≡b(mod\ m) a≡b(mod m)

下面的只要大概知道個概念就好

同余類：

亦稱剩余類，為數論的基本概念之一，設模為m，則根據余數可將所有的整數分為m類：

把所有與整數a模m同余的整數構成的集合叫做模m的一個剩余類，記作[a]，（也見過a上面加一杠的寫法）并把a叫作剩余類[a]的一個代表元，

例：在模5意義下，3、8、13都屬于同余類[3]

簡化剩余系：

同余類的集合構成了m的完全剩余系

簡化剩余系指m的完全剩余系中與m互質的數的集合

簡化剩余系關于模m乘法封閉，設a、b為簡化剩余系中任意兩個數，則a×b必然也屬于簡化剩余系

3.同余的性質

介紹在下面要用到的一些同余的性質

①若 a ≡ b ( m o d n ) a≡b(mod\ n) a≡b(mod n) 則 a ? c ≡ b ? c ( m o d n ) a*c≡b*c(mod\ n) a?c≡b?c(mod n)

②若 a ≡ b ( m o d n ) a≡b(mod \ n) a≡b(mod n) 則 a q ≡ b q ( m o d n ) a^q≡b^q(mod\ n) aq≡bq(mod n)

③若 a ≡ b ( m o d n ) , c ≡ d ( m o d n ) a≡b(mod\ n), c≡d(mod\ n) a≡b(mod n),c≡d(mod n)，則 a ? c ≡ b ? d ( m o d n ) a*c≡b*d(mod\ n) a?c≡b?d(mod n)

由乘法對于模運算的分配律可以證明↑

①②可由③推得

其他性質可參見百度百科

4.歐拉定理

若正整數a，n互質，則 a φ ( n ) ≡ 1 ( m o d n ) a^{φ(n)}≡1(mod \ n) aφ(n)≡1(mod n)

證明不會

費馬小定理其實就是歐拉定理在n為素數時的特殊情況

推論：

若a，n互質，b為任意正整數，則 a b ≡ a b m o d φ ( n ) ( m o d n ) a^b≡a^{b\ mod \ φ(n)}(mod \ n) ab≡ab mod φ(n)(mod n)

——————————————————————————

證明：

令 b = q ? φ ( n ) + r b=q*φ(n)+r b=q?φ(n)+r，則：

a b ≡ a q ? φ ( n ) + r ≡ ( a φ ( n ) ) q ? a r ≡ 1 q ? a r ≡ a r ≡ a b m o d φ ( n ) ( m o d n ) a^b≡a^{q*φ(n)+r}≡(a^{φ(n)})^{q}*a^r≡1^q*a^r≡a^r≡a^{b\ mod \ φ(n)}(mod \ n) ab≡aq?φ(n)+r≡(aφ(n))q?ar≡1q?ar≡ar≡ab mod φ(n)(mod n)

——————————————————————————

應用：

前面已經說明了，加減乘除的模運算處理方式，這個推論可以以應用于冪次運算的模運算處理方式

a b % p = ( a % p ) b % φ ( p ) a^b\%p=(a\%p)^{b\%φ(p)} ab%p=(a%p)b%φ(p)

當然，一般來說快速冪 l o g ( N ) log(N) log(N)級別的復雜度已經足夠優秀

引理：

a,n互質，滿足 a x ≡ 1 ( m o d n ) a^x≡1 (mod \ n) ax≡1(mod n)的最小正整數x一定是 φ ( n ) φ(n) φ(n)的約數

反證法：

假設滿足條件的最小正整數 x 0 x_0 x0?不是 φ ( n ) φ(n) φ(n)的約數

首先 a φ ( n ) ≡ 1 ( m o d n ) a^{φ(n)}≡1(mod \ n) aφ(n)≡1(mod n)是一定成立的，所以 x 0 < φ ( n ) x_0<φ(n) x0?<φ(n)

令 φ ( n ) = q ? x 0 + r ( 0 < r < x ) φ(n)=q*x_0+r\ (0<r<x) φ(n)=q?x0?+r (0<r<x)

因為 a x 0 ≡ 1 ( m o d n ) a^{x_0}≡1(mod\ n) ax0?≡1(mod n)

所以 a q ? x 0 ≡ ( a x 0 ) q ≡ 1 ( m o d n ) a^{q*x_0}≡(a^{x_0})^q≡1(mod \ n) aq?x0?≡(ax0?)q≡1(mod n)

因為 a φ ( n ) ≡ a q ? x 0 + r ≡ a a ? x 0 ? a r ≡ 1 ( m o d n ) a^{φ(n)}≡a^{q*x_0+r}≡a^{a*x_0}*a^r≡1(mod \ n) aφ(n)≡aq?x0?+r≡aa?x0??ar≡1(mod n)

所以 a r ≡ 1 ( m o d n ) a^r≡1(mod\ n) ar≡1(mod n)

因為r< x 0 x_0 x0? 所以假設不成立

5.貝祖定理

對任意整數a、b，存在一對x、y滿足 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)

證明：

歐幾里得演算法求gcd(a,b)時：

long long  gcd(long long  a,long long  b){
   return a%b==0?b:gcd(b,a%b);
}

遞回函式的終點是a%b==0，此時gcd(a,b)==b， a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)明顯是有解的，易得x=0，y=1為一組特解

運用數學歸納法，只要證明：

b ? x + ( a % b ) ? y = g c d ( b , a % b ) b*x+(a \% b)*y=gcd(b, a\%b) b?x+(a%b)?y=gcd(b,a%b)有解，則 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)必有解

那么貝祖定理就成立了

a % b = a ? b ? [ a / b ] ( [ a / b ] 表 示 整 除 ） a\%b=a-b*[a/b]\ ([a/b]表示整除） a%b=a?b?[a/b] ([a/b]表示整除）

b ? x + ( a % b ) ? y b*x+(a \% b)*y b?x+(a%b)?y

= = b ? x + ( a ? b ? [ a / b ] ) ? y ==b*x+(a-b*[a/b])*y ==b?x+(a?b?[a/b])?y

= = a ? y + b ? ( x ? [ a / b ] y ) ==a*y+b*(x-[a/b]y) ==a?y+b?(x?[a/b]y)

= = g c d ( b . a % b ) ==gcd(b.a\%b) ==gcd(b.a%b)

= = g c d ( a , b ) ==gcd(a,b) ==gcd(a,b)

所以令 x ′ = y , y ′ = x ? [ a / b ] y x^{'}=y,y^{'}=x-[a/b]y x′=y,y′=x?[a/b]y，則 a x ′ + b y ′ = g c d ( a , b ) ax^{'}+by^{'}=gcd(a,b) ax′+by′=gcd(a,b)

綜上，貝祖定理成立

6.擴展歐幾里得

由上述的思路，可以寫出擴展歐幾里得的演算法

代碼如下：

long long  exgcd(long long  a,long long  b,long long  &x,long long &y){
   if(a%b==0) {x=0;y=1;return b;}
   long long  d=exgcd(b,a%b,x,y);
   long long temp=x; x=y;y=temp-(a/b)*y;
   return d;
}

應用：

①解不定方程ax+by=gcd(a,b)

函式回傳的兩個值x，y就是不定方程的一組特解

對于更一般化的方程ax+by=c，它有解當且僅當 c % g c d ( a , b ) = = 0 c\%gcd(a,b)==0 c%gcd(a,b)==0

我們可以先解出ax+by=gcd(a,b)的一組特解，然后令其同時乘上 c g c d ( a , b ) \frac{c}{gcd(a,b)} gcd(a,b)c?即得方程ax+by=c的特解 x 0 , y 0 x_0,y_0 x0?,y0?

方程ax+by=c的通解可以表示為

x = x 0 + k ? b g c d ( a , b ) x=x_0+k\cdot \frac{b}{gcd(a,b)} x=x0?+k?gcd(a,b)b?

y = y 0 ? k ? a g c d ( a , b ) y=y_0-k\cdot \frac{a}{gcd(a,b)} y=y0??k?gcd(a,b)a?

求x的最小正整數解：

令 t e m p = b g c d ( a , b ) 令temp= \frac{b}{gcd(a,b)} 令temp=gcd(a,b)b?

則最小正整數解為 ( x 0 % t e m p + t e m p ) % t e m p (x_0\%temp+temp)\%temp (x0?%temp+temp)%temp

更正：此處并不是最小正整數解，而是最小非負整數解，在答案可能為0的時候需要特判

②解線性同余方程

擴歐可以解決這種形式的同余方程：ax≡c(mod b) (1<c<b)

該方程顯而易見可以轉化為不定方程ax+by=c

③求逆元：

逆元的定義 a ? a ? 1 ≡ 1 ( m o d p ) a*a^{-1}≡1(mod \ p) a?a?1≡1(mod p)

將逆元 a ? 1 a^{-1} a?1表示為x

則可以轉化為不定方程 a ? x + p ? y = 1 a*x+p*y=1 a?x+p?y=1

該方法相比于小費馬定理略顯麻煩，但是應用范圍更廣，只要求a、p互質即可，而小費馬定理要求p為質數

7.中國剩余定理

線性同余方程：

形如a*x≡b (mod m)的方程，因為未知數x的指數為1，所以稱為一次同余方程或線性同余方程

該方程要么無解，要么有無數個解

可以使用擴展歐幾里得演算法求解這類方程

一元線性同余方程組：

中國剩余定理（孫子定理）可以用于解決如下形式的線性同余方程組：

其中 m 1 , m 2 ? ? ? , m n m_1,m_2\cdot\cdot\cdot,m_n m1?,m2????,mn?是兩兩互質的整數

令 m = ∏ i = 1 n m i , M i = m / m i m=∏_{i=1}^nmi \ ,\ \ M_i=m/mi m=∏i=1n?mi , Mi?=m/mi

令 t i t_i ti?為線性同余方程 t i M i ≡ 1 ( m o d m i ) t_iM_i≡1(mod \ m_i) ti?Mi?≡1(mod mi?)的一個解，也就是 M i M_i Mi?的逆元

則方程組的整數解為 ∑ i = 1 n a i M i t i ∑_{i=1}^na_iM_it_i ∑i=1n?ai?Mi?ti?

證明：

首先解釋一下，一般的線性同余方程長這樣：a*x≡b (mod m)

它的解有無數個，我們可以將通解表示為 x = x 0 + k t ( k ∈ Z ) x=x_0+kt \ (k∈Z) x=x0?+kt (k∈Z)

而這個通解其實就相當于 x ≡ x 0 ( m o d t ) x≡x_0(mod\ t) x≡x0?(mod t)

因此所有的線性同余方程組都可以轉化為下面這種較為一般的形式

而孫子定理通過構造法得到了一種特殊情況下（即模數 m i m_i mi?兩兩互質時）的通解，換言之只要能保證模數兩兩互質則方程組一定有解

證明如下：

將解 ∑ i = 1 n a i M i t i ∑_{i=1}^na_iM_it_i ∑i=1n?ai?Mi?ti?代入原方程組任一方程

a 1 M 1 t 1 + a 2 M 2 t 2 + ? ? ? + a i M i t i + ? ? ? + a n M n t n ≡ a i ( m o d m i ) a_1M_1t_1+a_2M_2t_2+\cdot\cdot\cdot+a_iM_it_i+\cdot\cdot\cdot+a_nM_nt_n≡a_i(mod\ m_i) a1?M1?t1?+a2?M2?t2?+???+ai?Mi?ti?+???+an?Mn?tn?≡ai?(mod mi?)

上面這個式子顯然是成立的

對于 k ≠ i k≠i k?=i的項， a k M k t k ≡ 0 ( m o d m i ) a_kM_kt_k≡0(mod\ m_i) ak?Mk?tk?≡0(mod mi?)，因為 M k M_k Mk?是 m i m_i mi?的倍數

而 a i M i t i ≡ a i ( m o d m i ) a_iM_it_i≡a_i(mod\ m_i) ai?Mi?ti?≡ai?(mod mi?)，因為 t i t_i ti?是 M i M_i Mi?在模 m i m_i mi?意義下的逆元， t i M i t_iM_i ti?Mi?在模 m i m_i mi?意義下等價于1

證畢

方程組的通解可以表示為 x = ∑ i = 1 n a i M i t i + k m x=∑_{i=1}^na_iM_it_i+km x=∑i=1n?ai?Mi?ti?+km

中國剩余定理的板子就不放了，畢竟都是些常規操作

需要注意的是中國剩余定理成立的前提是 m i m_i mi?互質，不要求 m i m_i mi?為素數，所以在求 t i t_i ti?時不要使用小費馬定理，而應該用擴歐求逆元，在這里放一個擴歐求逆元的板子：

long long exgcd(long long a,long long b,long long &x,long long &y){
   if(a%b==0){x=0;y=1;return b;}
   long long d=exgcd(b,a%b,x,y);
   long long temp=x;
   x=y;y=temp-a/b*y;
   return d;
}

long long inv(long long m,long long mod){ //求m在模mod下的逆元
   long long x,y;
   long long d=exgcd(m,mod,x,y);
   if(d!=1) return -1; //若不互質則無逆元
   long long temp=mod/d;
   return (x%temp+temp)%temp; //回傳最小正整數解
}

8.一般的線性同余方程組

中國剩余定理成立的前提是每個方程的模數兩兩互質，對于其他情況則不適用

可以使用n次擴展歐幾里得演算法進行求解：

假設已經求出了前k-1個方程構成的方程組的解 x x x， m m m為前k-1個方程模數 m i m_i mi?的最小公倍數

則前k-1個方程的通解可以表示為 x + i ? m , i ∈ Z x+i*m,i∈Z x+i?m,i∈Z

為了使前k-1個方程的解也滿足第k個方程，只能從通解中尋找

x + i ? m ≡ a k ( m o d m k ) x+i*m≡a_k(mod \ m_k) x+i?m≡ak?(mod mk?)

只要尋找到滿足條件的i即可

對該方程進行轉化：

i ? m ≡ a k ? x ( m o d m k ) i*m≡a_k-x \ (mod \ m_k) i?m≡ak??x (mod mk?)

此時只有 i i i是未知數，所以這就是一個線性同余方程，用一次擴展歐幾里得就可得到它的一個解 i = t i=t i=t，則 x ′ = x + t ? m x^{'}=x+t*m x′=x+t?m就是前k個方程的一個解

以此類推就能得到整個方程組的解

而如果在某次用擴展歐幾里得運算時發現無解，則整個方程無解