亦稱抽屜原理。
常用於證明存在性證明(有兩個或以上)和求最壞情況(最差會有一個)下的解

經典問題就是鴿籠問題，若更為學術性則為將 \(n+1\) 個物體劃分為 \(n\) 個組別，則至少會有一個組別有兩個或以上的物體。
具體方法使用反證法 :
假設現在有 \(n+1\) 個物體，分成 \(n\) 組，則至少會有一組有 \(\lfloor \frac {n+1} n \rfloor +1\)個物體。
倘若每個組別都只有個 \(\lfloor \frac {n+1} n \rfloor\) 物體，則顯然是一組只有一個
那麼總和將會是總共有 \(1 \cdot n\) 個物體，與全部有 \(n+1\) 個物體不符合。

若今天推廣到 \(k\) 個物體，分成 \(n\) 組，則至少會有一組有 \(\lceil \frac k n \rceil\)個(或以上)個物體。
依然是使用反證法證明 :
假設現在有 \(k\) 個物體，分成 \(n\) 組，則至少會有一組有 \(\lceil \frac k n \rceil\)個物體。
倘若每個組別都只有 \(< \lceil \frac k n \rceil\) 個物體，則顯然
其物體總和會是 \((\lceil \frac k n \rceil -1) \cdot n = n \cdot \lceil \frac k n \rceil -n < n \cdot (\lfloor \frac k n \rfloor +1) -n \leq k\)
明顯不符。

實際應用在題目

關鍵點為製造抽屜(製造籠子)
ex : 給出 \(n\) 個數字，和整數 \(m(1 \leq m \leq n-1)\)，問說是否可以選出至少兩個數字都同餘 \(m\) 。

解題思路 : 製造 \(m\) 個籠子

模運算

整數在模空間底下計算，要讓計算結果在 \([0, m-1]\) 之間
加減乘可以直接做，但除法會發生甚麼事情呢?

(此為常用技巧)

\((a + b) \mod m = (a+b)\ \%\ m\)
\((a - b) \mod m = ((a-b)\ \%\ m + m)\ \%\ m\)
\((a \cdot b) \mod m = (a \cdot b)\ \%\ m\)
\((a\ /\ b) \mod m =\ ?\)

模逆元

發現除法會錯(也避免負數)之後，於是我們知道，需要 模 "逆元" !
在模 \(m\)意義下，對於一個整數 \(u\)，如果存在一個整數 \(v\)，使得 \(u \cdot v≡1(mod\ p)\)，則 \(v\)是 \(u\) 的逆元，記作 \(u^{−1}\)

因此對於 \((a\ /\ b)\mod m\)
如果找到 \(b\) 的模逆元就可以把除法運算改成乘法了

逆元性質以及證明

• 存在唯一性

  模p意義下，對於a而言，如果其存在逆元，則逆元只有一個\(a′ = a^{−1}\)。
  可使用反證法或演譯法證明。

• 完全積性函數

  也就是 \((a \cdot b)^{−1}≡a^{−1} \cdot b^{−1}(mod \ p)\)
  考慮有 \(a \cdot a^{−1}≡1(mod \ p)\)，和\(b \cdot b^{−1}≡1(mod \ p)\)，乘到一起就是\((a \cdot b)(a^{−1}×b^{−1})≡1(mod \ p)\)，所以\((a \cdot b)^{−1}≡a^{−1}×b^{−1}(mod \ p)\)

證明參考

於是就可以發現除法可以變成\((a\ /\ b) \equiv (a\ \times\ b^{-1}) \mod m\)

費馬小定理

如果 \(a, m\) 互質的情況下

\(a^m \equiv a (\mod m)\)

\(\to\)

\(a^{m-1} \equiv 1 (\mod m)\)

\(\to\)

\(a^{m-2} \equiv a^{-1} (\mod m)\)

因此求出 \(a^{m-2}\) 即為 \(a\) 的模逆元
而當 a, m 不互質 ( gcd \(\ne\) 1) 的情況下模逆元不存在

因此在 \(b\) 與 \(m\) 互質的情況下
要求出 \(a / b\) 可以求出

\((a\ /\ b) \equiv (a\ \times\ b^{m-2}) \mod m\)

而 \(b^{m-2}\) 可以透過快速冪求出

通常需要取模的題目給的 \(m\) 都會是很大的質數 (\(10^9+7, 998244353\)) 等
所以通常 \(b\) 會跟 \(m\) 互質

\(n\) 個東西要取 \(m\) 個的方法數為 \(C_m^n = \frac{n!}{m!(n-m)!}\)

如果題目要求某個組合數 \(\mod p\)

則根據剛剛的模逆元可以得到

\(\frac{n!}{m!(n-m)!} \equiv n! \times\) inverse\((m!)\) \(\times\) inverse\(((n-m)!) \equiv\)

\(n! \times (m!)^{p-2} \times ((n-m)!)^{p-2}\) \((\)mod \(p)\)

而如果題目是多筆測資，會發現 \(C_m^n\) 會算很多次，
也就是每次會 O(\(N\)) 在算階乘 跟 O(\(lg(p)\)) 算模逆元

因此通常會先建表
對於階乘直接邊乘邊取餘數
模逆元則是根據建好的階乘表，
先快速冪算出 inverse(n!)，而 inverse((n-1)!) 即為 inverse(n!) * n

因此可以再 O(\(N + lgN\)) 的時間建出所有 \(\le N\) 的階乘與模逆元

#define MXN 1'000'005
#define N 1'000'000
long long fac[MXN], inv[MXN];
fac[0] = 1; // 0! = 1
for(long long i = 1; i <= N; i++)    
    fac[i] = fac[i-1] * i % MOD;
inv[N] = FastPow(fac[N], MOD-2); // 快速冪
for(long long i = N-1; i >=0; i--)
    inv[i] = inv[i+1] * (i+1) % MOD;

計算兩個數字 \(a\) , \(b\) 的最大公因數 \(gcd(a,b)\)
同時在程式實作裡，我們會使用輾轉相除法進行實作。
即 \(gcd(a,b)=gcd(b,a \ mod \ b)\) \(a\) , \(b\) 非負且 \(a\ge b\)
輾轉相除法求解最大公因數並不是唯一方法，但相當快速。

具體實作

int gcd(int a, int b) {
    int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

那其實也可以寫成

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

當然也可以直接呼叫預設函式

since C++14

#include<algorithm> 
__gcd(a,b);

since C++17

#include<numeric> 
gcd(a,b);

裴蜀定理

對於不定方程\(ax+by=m\)的整數解
其有解的充要條件為 \(gcd(a,b)|m\)

若 \(a\) , \(b\) 是整數,且 \(gcd(a,b)=d\)，那麽對於任意的整數 \(x\) , \(y\) , \(a x + b y\) 都一定是 \(d\) 的倍數，一定存在整數 \(x\) , \(y\) ，使 \(a x + b y = d\) 成立

證明

我們設 \(a ≤ b\)，由輾轉相除法的過程\((gcd(x,y)=gcd(y, x \%\ y))\)
設\(b=ax_1+r_1\)，那麽\(b \%\ a\) 後 \(b=r_1\)

則可以拓展出以下式子:

\(b=a \cdot x_1+r_1\)
\(a=r_1 \cdot x_2+r_2\)
\(r_1=r_2 \cdot x_3+r_3\)
.
.
.
\(r_{k-3}=r_{k−2} \cdot x_{k−1}+r_{k−1}\)
\(r_{k-2}=r_{k−1} \cdot x_{k}+r_{k}\)
\(r_{k-1}=r_{k} \cdot x_{k+1}+r_{k+1}\)

因為輾轉相除法除到最後餘數為 0，在這，我們設 \(r_{k+1}=0\)，那麼， \(r_k\) 就是 \(a\) 和 \(b\) 的最大公因數，即 \(r_k = d\)。將 \(r_k = d\)帶入上式中可以移項得到
\(d=m_1 \cdot r_{k−2}+n_1 \cdot r_{k−3}\)

由於其中會用到的數字都是整數，在推論到最後會發現式子會變成
\(d=m_k \cdot a+n_k \cdot b\)

於是得證，\(ax + by = d\) 有整數解

最後，需要證明方程\(ax+by=z\)，只有滿足 \(gcd (a,b)∣z\) ，方程才有整數解。

裴蜀定理在歐幾里得上的應用

於是，知道\(ax+by=m\)的整數解其有解的充要條件為 \(gcd(a,b)|m\) 後，就可以回到正題，要如何在已知 \(a\) , \(b\) 的情況求解式子裡的\(x\) , \(y\)

設當前的式子為 \(ax_1 + by_1 = gcd(a,b)\)，根據歐幾里得算法，存在式子
\(bx_2+(a \ mod \ b)y_2 = gcd (b,a  mod  b)\)

\(∵ a \ mod \ b = a − \lfloor \frac a b \rfloor \cdot b\)
\(∴ ax_1 + by_1 = bx_2 + (a− \lfloor \frac a b \rfloor \cdot b)y_2\)
\(ax_1 + by_1 = bx_2 + ay_2 − \lfloor \frac a b \rfloor \cdot b \cdot y_2\)
\(ax_1 + by_1 = ay_2 + b(x_2 − \lfloor \frac a b \rfloor \cdot y_2 )\)

\(∴ x_1 = y_2 , y_1 = x_2 − \lfloor \frac a b \rfloor \cdot y_2\)

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

exgcd 還有甚麼用途呢?可以用來求逆元。
求 \(a\) 在模 \(p\) 意義下的逆元
倘若使用費馬小定理則需要保證p為質數，使用 exgcd 則不需要。

設 \(x\) 為 \(a\) 在模 \(p\) 意義下的逆元，那麼滿足式子：
\(ax \equiv 1 (mod \ p)\)

那麼有：
\(ax + my = 1\)
然后用 exgcd 求出 \(x\) 即可

long long inv(long long a,long long m){
    long long x,y;
    long long d=exgcd(a,m,x,y);
    if(d==1) return (x+m)%m;
    else return -1; //-1為無解
}

Problem

NCPC 2020 final

input
3
2 3 5
4 4 3
13 5 7

output
2
1
5

只需要移項完式子後使用三分搜搜索 \(x\) 及 \(y\) 即可，會發現他的 \(x\) 值以及 \(y\) 值的圖形是為一個斜線(直線)，所以只需要使用三分搜查詢到那兩個點，就可以確定答案。

也是韓信點兵那些的經典例題，應該要對這些東西很熟悉
中國剩餘定理:設正整數 \(m_1\) , \(m_2\) …… \(m_k\) 兩兩互質，則同餘方程組求解 \(x\)

\(x \equiv a_1 \pmod {m_1}\)
\(x \equiv a_2 \pmod {m_2}\)
\(x \equiv a_3 \pmod {m_3}\)
.
.
.
\(x \equiv a_{k-2} \pmod {m_{k-2}}\)
\(x \equiv a_{k-1} \pmod {m_{k-1}}\)
\(x \equiv a_{k} \pmod {m_{k}}\)

那如何求 \(x\) 呢?
過程:

1. 計算所有模數的積 \(n\)
2. 對於第 \(i\) 個方程：
   計算 \(M_i=\frac{n}{m_i}\)
   計算 \(M_i\) 在模 \(m_i\) 意義下的 逆元 \(M_i^{-1}\)

方程組在模 \(n\) 意義下的唯一解為：\(x=\sum_{i=1}^k a_i \cdot M_i \cdot M_i^{-1} \pmod n\)

實作方式 會使用到模逆元，也就是會用到拓展歐幾里得

#define LL long long
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    int now=exgcd(b, a % b, y, x);
    y -= a / b * x;
    return now;
}
LL CRT(LL k, LL* a, LL* r) {
    LL n = 1, ans = 0;
    for (LL i = 1; i <= k; i++) {
        n = n * r[i];
    }
    for (LL i = 1; i <= k; i++) {
        LL m = n / r[i], b, y;
        exgcd(m, r[i], b, y);
        ans = (ans + a[i] * m * b % n) % n;
    }
    return (ans % n + n) % n;
}

Problem

NCPC 2018 final

input
3
2 4 1
4 5 9
1 2 4
2 5 7
0 0 1
2 5 127

output
154
67
890

跟範例程式碼差不多，只需要稍微確認輸入的順序，以及好好的初始化，然後套入程式碼即可。

在 \(N\) 個集合 \(A_1, A_2,..., A_n\)裡，如果要算出這 \(N\) 個集合的聯集

\(|\bigcup\limits_{i=1}^{N} A_i| =\)

\(\sum\limits_{i=1}^{N}|A_i| - \sum_{1 \le i < j \le N}|A_i\cap A_j| + \sum_{1 \le i < j < k \le N}|A_i\cap A_j\cap A_k| - ...\)
\(+ (-1)^{N-1}|A_1\cap ...\cap A_N|\)

一個集合 減去 兩個集合的交集 加上 三個集合的交集 … 直到算出所有可能的交集為止。

使用之前教過的，大家也看過的圖片當作例子

二項式定理

要如何知道每個集合之間的聯集要加幾次，上圖片

會發現可以充分利用帕斯卡三角形的性質，對於每一個項數去進行補充或削減，直到每個元素的出現次數皆為\(1\)時即可。

例題 CSES 2185. Prime Multiples

給你數字 \(N, M\)
給 \(N\) 個相異質數
問在 \(1\sim M\) 之間有幾個數字為至少一個給定的質數的倍數

• \(1 \le N \le 20\)
• \(1 \le M \le 10^{18}\)

sample

N = 3, M = 15
質數為 {2, 5, 7}

10
(2,4,5,6,7,8,10,12,14,15)

因此 \(N\) 個集合為 第 \(i\) 個質數的倍數
要求出 \(1\sim M\) 之間的數字所有集合的聯集

以範例來說
\(|2|\) + \(|5|\) + \(|7|\) - \(|2\cap 5|\) - \(|2\cap 7|\) - \(|5\cap 7|\) + \(|2\cap 5\cap 7|\)

因此答案為 7 + 3 + 2 - 1 - 1 - 0 + 0 = 10

範例程式碼

for (int i = 1; i < 1<<k; i++) {
    int x = -1;
    if (__builtin_popcount(i)&1) x = 1;
    int y = n;
    int z = 1;
    for (int j = 0; j < k; j++) {
        if (i>>j&1) {
            if (z >= n/a[j] + 1) {
                z = INF;break;
            }
            z = z*a[j];
        }
    }
    y /= z,ans += x*y;
}

## 練習 題單