基礎數論知識總結

1.  費馬小定理與擴充歐幾裡得在乘法逆元上的運用

費馬小定理

a phi(n)−1 ≡1(modn) 

擴充歐幾裡得

a⋅x≡1(modn) 

乘法逆元

針對 ba modn  這種除法取模，将它轉換為乘法取模，我們需要用到之前的費馬小定理和擴充歐幾裡得，這兩種方法都可以将除法取模變為乘法取模，什麼時候用哪種，後續會說到

費馬小定理處理乘法逆元

f(n)=ba modn(1) 

a phi(n)−1 ≡1(modn)(2) 

1=h(n)=a phi(n)−1 modn(3)←(2) 

由 f(n)  和 h(n)  相乘可以得到如下公式:

f(n)⋅h(n)=f(n)⋅1=b⋅a phi(n)−2 modn(4) 

其中 phi(n)  為歐拉函數即小于n并且與n互質的個數

如果 n  為質數的話,phi(n) 很明顯為 n−1  ,因為任意正整數都要質數互質，是以公式就變成了 b⋅a n−2  

如此我們就可以通過快速幂來處理 b⋅a n−2  

擴充歐幾裡得處理乘法逆元

f(n)=ba modn(1) 

a⋅x≡1(modn)(2) 

1=h(n)=a⋅xmodn(3)←(2) 

由 f(n)  和 h(n)  相乘可以得到如下公式:

f(n)⋅h(n)=f(n)⋅1=b⋅xmodn(4) 

求出 x  後就可以将ba modn 求出.

在求解 x  的過程中(2) 式可以看成是 a⋅x+n⋅y=1  .

a⋅x≡1(modn)(2) 

a⋅x−n⋅y=1(5)←(2) 

a⋅x+n⋅y=1(6)←(5) 

由 (6)  式可以看出要想 x  和y 存在整數解 gcd(a,b)  必須等于 1 

不管是費馬小定理還是擴充歐幾裡得如果要進行乘法逆元的話必須要滿足一個條件gcd(a,n)==1 即 a  和n 必須要互質否則兩個公式都是不能夠使用的. [  擴充歐幾裡得算法下述有講解] 

何時使用處理乘法逆元

1.  當 n  為質數的時候一般用費馬小定理，因為 b n−2 modn 

2.  當時間限制比較緊的時候使用費馬小定理，因為它可以使用快速幂進行求解

3.  其它的情況則是依照題目要求而定，當然，使用費馬小定理處理乘法逆元的比較多，擴充歐幾裡得在求解方程式的整數解上有着強大的作用

2.  擴充歐幾裡得真解

歐幾裡得算法

在講解擴充歐幾裡得之前

講解歐幾裡得算法是必要的，所謂的歐幾裡得即求解最大公約數。

算法代碼:

/*
    作用:求解最大公約數(歐幾裡得)
    方法：輾轉相除法
*/
int gcd(int a, int b){
    return b ? gbc(b, a % b) : a;
}
           

擴充歐幾裡得算法

擴充歐幾裡得可以求解出 a⋅x+b⋅y=gcd(a,b)  中一個滿足方程式的 [  整數] 特解

g=gcd(a,b)(1) 

a⋅x+b⋅y=g(2) 

b⋅x1+(amodb)⋅y1=g(3) 

我們需要針對 (2)  和 (3)  找出他們之間的規律

很明顯

amodb=a−⌊ab ⌋⋅b(4) 

是以由 (3)  和 (4)  可得 (5) 

b⋅x1+(a−⌊ab ⌋⋅b)⋅y1=g(5) 

化簡 (5)  為 (6) 

a⋅y1+b⋅(x1−⌊ab ⌋⋅y1)=g(6) 

我們聯合 (2)  和 (6)  ,可以得出下述公式：

x=y1 

y=x1−⌊ab ⌋⋅y1 

其中我們書寫代碼的終止條件：

gcd(a,0)=a  為其終止點

a⋅1+0⋅0=a 

是以當 b=0  時， x=1  ， y=0 

如此我們就可以寫出求解擴充歐幾裡得算法的遞歸代碼：

void ex_gcd(int a,int b, int &d, int &x, int &y){
    if(!b){
        x = 
        y = ;
        d = a;
        return;
    }
    ex_gcd(b, a % b, d, y, x);
    y -= x * (a / b);
}
           

最終求出的 x  ，y 為 a⋅x+b⋅y=gcd(a,b)  的一個特解

然而解是可能有多個，因為 a⋅x+b⋅y=gcd(a,b)  可能是條直線

是以如何得知其它解呢

我們假設如果存在另外一個解 x2  ， y2  ，那麼可以列出下列方程：

a⋅(x1−x2)=b⋅(y2−y1) 

兩邊同時除以g

a ′ ⋅(x1−x2)=b ′ ⋅(y2−y1) 

其中 a ′ =ag   ， b ′ =bg   ，且 a ′   和 b ′   一定互素，那麼 (x1−x2)  一定為 b ′   的倍數，即 (x1−x2)=k⋅a ′   ,代入公式得

(y2−y1)=k⋅a ′  

是以 a⋅x+b⋅y=gcd(a,b)  的一個特解為 (x0，y0)  的話，那麼其任意整數解都可以寫成 (x0+k⋅b ′ ，y0−k⋅a ′ ) 

如果我們要求解 a⋅x+b⋅y=c  的整數解呢 ? 

大家也應該想到了答案就是(x0⋅cg ，y0⋅cg ) 

如果 cmodg≠0  則表示沒有整數解。

3.  歐拉函數

歐拉函數，縮寫 ϕ  ，程式中一般用 phi(n)  來表示，求解出小于n且與n互質的正整數的個數

我們針對一個 n  ，可以将它化為如下式子：

n=p q 1  1 ⋅p q 2  2 ⋅p q 3  3 ⋅⋅⋅⋅p q n  n  

進而可以得出如下公式：

phi(n)=n⋅(1−1p 1  )⋅(1−1p 2  )⋅(1−1p 3  )⋅⋅⋅⋅(1−1p n  ) 

簡化：

phi(n)=n⋅(p 1 −1p 1  )⋅(p 2 −1p 2  )⋅(p 3 −1p 3  )⋅⋅⋅⋅(p n −1p n  ) 

通過下述公式我們可以寫出如下代碼：

/*
 *函數名稱：phi
 *參數n：需要求解的歐拉函數值
*/
int phi(int n){
    int res = n;//int -> LL
    for(int i = ;i <= sqrt(n);i ++){
        if(n % i == ){
            res = res / i * (i - );
            while(n % i == ) n /= i;
        }
    }
    if(n > ) res = res / n * (n - );
    return res;
}
           

先進行除法是為了防止中間資料溢出

歐拉函數求出的結果有以下幾種性質：

1.  除了 n=2  外， phi(n)≡0(mod2)  即 phi(n)  求出的結果為 [  偶數] 

2.phi(n)  為積性函數，但不是完全積性函數， phi(n⋅m)=phi(n)⋅phi(m)  當且僅當 gcd(n,m)==1  時成立

3.  一個數的所有質因子之和為： phi(n)⋅n2   .因為 gcd(n,i)==1  是以 gcd(n,n−i)==1  ,如此 f(n)=(a 1 +n−a 1 )+(a 2 +n−a 2 )+⋅⋅⋅+(a n +n−a n )  由于 a n   和 n−a n   都是與 n  互質，是以最終的結果f(n)=phi(n)⋅n ，由于算了兩倍質數，是以最後要除以 2  ，得出phi(n)⋅n2  .

單單以第一份代碼求解的話，求解一個數的歐拉函數值的複雜度為 O(sqrt(n))  ，是以求解n範圍内每一個數的歐拉函數值的複雜度為 O(n⋅sqrt(n))  ，很明顯，當資料大于 10 5   以上後明顯是不夠看的。我們可以根據求解大範圍素數的方法求解歐拉函數值即篩選法求歐拉函數值.

代碼如下：

const int MAXN =  + ;
int phiArr[MAXN];

void phi(void) {
    phiArr[] = ;
    for(int i = ; i < MAXN; i ++) {
        phiArr[i] = i;
    }
    for(int i = ; i < MAXN; i ++) {
        if(phiArr[i] == i) {
            for(int j = i; j < MAXN; j += i) {
                phiArr[j] = phiArr[j] / i * (i - );
            }
        }
    }
}
           

積性函數，何為積性函數？

對于正整數 n  的一個算術函數f(n) ，若 f(1)=1  ，且當 a  ，b 互質時 f(a⋅b)=f(a)⋅f(b)  ，在數論上就稱它為積性函數，若對于某積性函數 f(n)  ，就算 a  ， b 不互質，也有 f(a⋅b)=f(a)⋅f(b)  ，則稱它為完全積性函數

4.  同餘與模

1.(a+b)modn=((amodn)+(bmodn))modn 

2.(a−b)modn=((amodn)−(bmodn)+n)modn 

3.(a⋅b)modn=(amodn)⋅(bmodn)modn 

常見同餘與模例子:

1234=((1×10+2)×10+3)×10+4 

如果 1234  對 n  取模的話：

1234modn=((1×10modn+2modn)×10modn+3modn)×10modn+4modn 

5.  容斥定理

|A 1 ⋃A 2 ⋃A 3 ⋅⋅⋅A m |=∑ 1≤i≤m |A i |−∑ 1≤i<j≤m |A i ⋂A j |+∑ 1≤i<j<k≤m |A i ⋂A j ⋂A k |+⋅⋅⋅+(−1) m−1 ⋅∑ 1≤i 1 <i 2 <i 3 ⋅⋅⋅i n ≤m |A i 1  ⋂A i 2  ⋂A i 3  ⋅⋅⋅⋂A i n  | 

它的計算規律無非四個字：奇加偶減即奇數個則加，偶數個則減

用法：

容斥定理主要在處理質因子方面有着不菲的作用，大家不要糾結容斥定理的由來，隻需記住針對每一個集合，奇加偶減即可

如何實作容斥定理?

1.  二進制狀态壓縮

代碼：

void solve(){
    for(int i = ;i <  << m;i ++){
        int bits = ;
        for(int j = ;j < m;j ++){
            if(i >> j & ){
                bits ++;
                //根據題目而進行操作
            }
        }
        if(bits & ) {
            //奇數進行加法處理
        }
        else{
            //偶數進行減法處理
        }
    }
}
           

2.  DFS處理

代碼：待補充

3.  隊列數組

代碼：待補充

常見用法

1.  求解 [1,r]  中與 n  不互質的個數

int solve(int r) {
    int sum = ;
    for(int i = ; i <  << m; i ++) {
        int bits = , muls = ;
        for(int j = ; j < m; j ++) {
            if(i >> j & ) {
                bits ++;
                muls *= primes[j];
            }
        }
        int cur = r / muls;
        if(bits & ) {
            sum += cur;
        } else {
            sum -= cur;
        }
    }
    return sum;
}
           

6. 矩陣運算

矩陣運算規則

1.  矩陣相乘

⎡ ⎣ ⎢ x1y1z1 x2y2z2 x3y3z3 ⎤ ⎦ ⎥ ⋅⎡ ⎣ ⎢ xx1yt1zz1 xx2yy2zz2 xx3yy3zz3 ⎤ ⎦ ⎥  

針對上述矩陣相乘運算的兩個矩陣必須滿足一個條件，前者的行等于後者的列，同時如果前者為 n×m  ，後者為 k×n  ，最後形成矩陣的行列則為 k×n 

最後形成矩陣的某一行為 n  某一列為m ,那麼這個點的值則為第一個矩陣第 n  行和第二個矩陣第m 列一一相乘，即 mat(n,m)=mat1[n−1][0]⋅mat2[0][m−1]+mat1[n−1][1]⋅mat2[1][m−1]+⋅⋅⋅+mat1[n−1][k]⋅mat2[k][m−1] 

這裡要記清楚，兩矩陣相乘，前者的行等于後者的列，所有都為 k 

2. 矩陣相加和相減

⎡ ⎣ ⎢ x1y1z1 x2y2z2 x3y3z3 ⎤ ⎦ ⎥ +/−⎡ ⎣ ⎢ xx1yt1zz1 xx2yy2zz2 xx3yy3zz3 ⎤ ⎦ ⎥  

運算規則為對應的行列相加或相減

矩陣快速幂

和單純的求數字的幂的快速幂的原理是一樣的

代碼：

const int mod = ;
typedef long long LL;
typedef vector<LL>vec;
typedef vector<vec>mat;

/*
 *函數名稱：mul
 *參數A：進行矩陣乘法的第一個矩陣
 *參數B：進行矩陣乘法的第二個矩陣
*/
mat mul(mat &A, mat &B) {
    mat C(A.size(), vec(B[].size()));
    for(int i = ; i < A.size(); i ++) {
        for(int k = ; k < B.size(); k ++) {
            for(int j = ; j < B[].size(); j ++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}
/*
 *函數名稱：pow
 *參數A：進行快速幂矩陣
 *參數n：幂的次數
*/
mat pow(mat A, LL n) {
    mat B(A.size(), vec(A.size()));
    for(int i = ; i < A.size(); i ++) B[i][i] = ;
    while(n) {
        if(n & ) B = mul(B, A);
        A = mul(A, A);
        n >>= ;
    }
    return B;
}
           

7.  康托展開及其逆運算

用法

給予一個目标序列，求解他的全排列過程中，目标序列是第幾個排列

康托展開–示範案例

找出序列 [4,5,2,3,1]  在這個排列中的是第幾個排列

整個序列中比 4  小的數有3 個

整個序列中比 5  小的數有4 個但 4  已經在之前出現過了是以是3 個

整個序列中比 2  小的數有1 個

整個序列中比 3  小的數有兩個但2 已經在之前出現過了是以是 1  個

整個序列中比1 小的數有 0  個

那麼[4,5,2,3,1] 在這個排列中的順序是 3⋅4!+3⋅3!+1⋅2!+1⋅1!+0⋅0!+1=94 

我們可以發現，所謂的第幾個則是在這個數出現之前未出現的數中少于某個這個數的個數乘以該位的階乘。

将問題簡化，我們最終就是求 [  該位之後有多少個比該位小的數] 。

實作代碼：

typedef long long LL;
LL F[ + ];
void init(){
    F[] = ;
    for(int i = ;i <= ;i ++){
        F[i] = F[i - ] * i;
    }
}
/*
 *函數名稱：cd_cal
 *參數A：進行判斷序列
 *參數n：序列長度
*/
LL cd_cal(int *A, int n){
    LL ret = L;
    for(int i = ;i < n;i ++){
        int num = ;
        for(int j = i + ;j < n;j ++){
            if(A[i] > A[j]) num ++;
        }
        ret += F[n - i - ] * num;
    }
    return ret;
}
           

康托逆展開

所謂康托逆展開即給予一個長度為n的序列，讓你求出第m個排列是什麼

康托逆展開–示範案例

一個數量為 5  的排列，現在要你找出第96 種排序序列是什麼

首先用 96−1  得到 95  (将他本身這一個種給删掉，可以直接判斷)

用 95  去除 4!  得到 3  餘23 

用 23  去除 3!  得到 3  餘5 

用 5  去除2! 得到 2  餘1 

用 1  去除1! 得到 1  餘0 

有 3  個數比它小的數是4 

是以第一位是 4 

有3 個數比它小的數是 4  但4 已經在之前出現過了是以是 5  （因為4 在之前出現過了是以實際比 5  小的數是3 個）

有 2  個數比它小的數是3 

有 1  個數比它小的數是2 

最後一個數隻能是 1 

是以這個數是[4,5,3,2,1] 

在這裡我們又可以将問題簡化為求解 [  從1開始計數有多少個沒有被通路過的數] .

實作代碼:

typedef unsigned long long uLL;
uLL F[ + ],B[ + ];
bool vis[ + ];
void init() {
    F[] = ;
    for(int i = ; i <= ; i ++) {
        F[i] = F[i - ] * (uLL)i;
    }
}
/*
 *函數名稱：cd_cal
 *參數A：排列結果儲存數組
 *參數n：序列長度
 *參數v：第幾種排列
*/
void cd_cal(uLL *A, uLL n, uLL v) {
    memset(vis, false, sizeof(vis));
    v --;
    for(int i = ; i < n; i ++) {
        uLL k = v / F[n - i - ];
        v %= F[n - i - ];
        int c = k + , a = , f = -;
        while(a <= c) {
            f ++;
            if(!vis[f]) a ++;
        }
        A[i] = f;
        vis[f] = true;
    }
}
           

8.  錯排原理

何為錯排？

給定一個 n  長的序列，讓每一個數都不在原來位置上的擺放次數.

錯排公式

D(n)=(n−1)⋅[D(n−2)+D(n−1)] 

其中 D(n)  表示将 n  個物品進行錯排可以有多少種擺放方式.

錯排公式原理講解

1. 第一種了解方法

   分為兩種情況：

   1. 在原來i−1 個已經進行了錯排處理的物品的基礎上多加了一個元素 k  ，這個元素可以放在i−1 個已經進行了錯排處理的序列中任意一個位置，是以有 (i−1)⋅D(i−1)  種.
      • 如果 i−1  個數中有一個沒有進行錯排，那麼這個數與 k  進行交換，接着剩下的所有元素進行錯排有(i−1)⋅D(i−2) 個.
      • 如此答案為 D(n)=(n−1)⋅[D(n−2)+D(n−1)]  .

      • 第二種了解方法

        第一步，将第 n  個元素放在任意一個位置，比如位置k ，一共有 n−1  種放的方法.

        第二步，由于位置 k  處已經被第n 個元素給占據了，是以原本在位置 k  的元素需要放置在其他位置.

        這裡分為兩種情況：

        1. 将原本位置k 的元素直接放置在原本第 n  個元素所在的位置，則有(i−1)⋅D(n−2) 種.
        2. 在第一種情況的基礎上，将已經放置在位置 k  的第n 個元素和這個位置 k  給删除掉，如此我們又重新得到一個新的序列，這個序列的長度減少了一個，同時沒有了第n 個元素，原本在位置 k  的元素取代了第n 個元素，将這 n−1  個元素進行錯排後再将原本删除掉的位置 k  和第n 個元素放回來就構成了 (i−1)⋅D(n−1)  種.
        3. 如此答案為 D(n)=(n−1)⋅[D(n−2)+D(n−1)]  .

           9.  lucas  定理

           何為 lucas  定理

           用于求解 C(nm)%p  ,其中 p  是質數.

           公式

           lucas(n,m,p)=lucas(np ,mp ,p)×C(n%pm%p) 

           lucas(n,0,p)=1 

           證明

           沒明白，事後補上

           代碼模闆

           LL mod_pow(LL x, LL n, LL mod){
               LL ret = ;
               while(n > ){
                   if(n & ) ret = ret * x % mod;
                   x = x * x % mod;
                   n >>= ;
               }
               return ret;
           }
           
           LL C(LL m, LL n, LL p){
               if(n < m) return ;
               if(m > n - m){
                   m = n - m;
               }
               LL up = , down = ;
               for(LL i = ;i < m;i ++){
                   up = up * (n - i) % p;
                   down = down * (i + ) % p;
               }
               return up * mod_pow(down, p - , p) % p;// 
           }
           
           LL lucas(LL m, LL n, LL p){
               if(m == ) return ;
               return C(m % p, n % p, p) * lucas(m / p, n / p, p) % p;
           }
                      

           知識點未完，敬請期待！