Number Theory - HackMD

<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Number Theory Introduction to Competitive Programming 3/27 ---- * 鴿籠原理 :dove_of_peace: * 模運算 & 模逆元 * 組合數 * 錯排公式 * 卡塔蘭數 * 排容定理(求聯集) * 輾轉相除法 * 拓展歐幾里得(求逆元，求方程解) --- ## 鴿籠原理 :dove_of_peace: ![image](https://hackmd.io/_uploads/B1VxkVH21e.png) ---- ### :dove_of_peace: :dove_of_peace: :dove_of_peace: :dove_of_peace: 一句話概括：「 $n+1$ 個鴿子要飛進 $n$ 個籠子裡，必定有一個籠子將有 $2$ 隻以上個鴿子」以下證明一下(使用反證法)： - 假設現在有 $n+1$ 個鴿子，分成 $n$ 組，則至少會有一組有 $\lfloor \frac {n+1} n \rfloor +1$個鴿子。 - 倘若每個組別都只有個 $\lfloor \frac {n+1} n \rfloor$ 鴿子，則顯然是一組只有一個那麼總和將會是總共有 $1 \cdot n$ 個鴿子，與全部有 $n+1$ 個鴿子不符合。 ---- ### :dove_of_peace: :dove_of_peace: :dove_of_peace: :dove_of_peace: 若今天推廣到 $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$ 明顯不符。 ---- ## 例題 : 有 $n$ 隻鴿子($1$~$n$)，每隻有自己的數字 $a_i$。你需要在這 $n$ 隻裡面取一些鴿子，使得你取出來的鴿子數字總和為 $k$ 的倍數。沒辦法取的話就輸出無解。 $1 \leq k \leq n \leq 10^5$ $1 \leq a_i \leq 10^5$ ---- 我們可以先試著想想是否有可行解，怎麼下手呢？ ---- 考慮定義 $S_i$ 為 $a_1$ 至 $a_i$ 的前綴和，並令 $S_0 = 0$。這時我們將會有最多 $n+1$ 種前綴數字，這時考慮把這 $n+1$ 種前綴數字都去模 $k$ ( $\% k$ )。由於 $k \leq n$ ，模 $k$ 之後，$S_0$ 至 $S_n$最多有 $k$ 種可能的值 ( $0$ ~ $k-1$) ---- 可以生成 $k$ 個籠子，把 $n+1$ 個 $S_i$ 丟進去。根據鴿籠原理，可以假設 $S_l$ 跟 $S_r$ 撞在同一個籠子裡(餘數相同)，這時不難發現 $S_r - S_l ≡ 0$ mod $k$，代表取 $a_{l+1}$ 至 $a_{r}$ 就會是一組可能的解。以上證明不僅證明了是否有解，還證明了怎麼求解，讚讚！ --- ## 模運算 & 模逆元 ---- ## 模運算整數在模空間底下計算，要讓計算結果在 $[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 =\ ?$ ---- 除法會對嗎？舉一個例子：$4 \div 3$ mod $7$ 如果直接除則會產生小數($1.33333...$)，這違反模運算的規則：指允許計算過程中出現小數其合理的解為 $x = 6$，因為 $x \equiv \frac{4}{3}$ mod $7$ $\rightarrow 3x \equiv 4$ mod $7$ $\rightarrow 3\cdot 6 \equiv 4$ mod $7$ $\rightarrow 18 \equiv 4$ mod $7$ 那我們要怎麼得到x呢？模逆元！ ---- ## 模逆元在模 $m$意義下，對於一個整數 $u$，如果存在一個整數 $v$，使得 $u \cdot v≡1(mod\ p)$，則 $v$是 $u$ 的逆元，記作 $u^{−1}$ 因此對於 $(a\ /\ b)\mod m$ 如果找到 $b$ 的模逆元就可以把除法運算改成乘法了 #### 對證明和其性質有興趣可以看[這篇](https://www.cnblogs.com/ac-evil/p/12680705.html) ---- ## 費馬小定理如果 $a, m$ 互質，且 $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$ 互質 ```cpp! const int mod = 1000000007; fpow(b,mod-2);//fpow為快速冪 ``` 複雜度：$O(\log m)$ ( 快速冪的複雜度 ) --- ## 組合數 ![image](https://hackmd.io/_uploads/Hy51K4rn1g.png) ---- ## $C_k^n$ $n$ 個東西要取 $k$ 個的方法數為 $C_k^n = \frac{n!}{k!(n-k)!}$ 如果題目要求某個組合數 $\mod p$ 則根據剛剛的模逆元可以得到 $\frac{n!}{k!(n-k)!} \equiv n! \times$ inverse$(k!)$ $\times$ inverse$((n-k)!) \equiv$ $n! \times (k!)^{p-2} \times ((n-k)!)^{p-2}$ $($mod $p)$ ---- 通常會先建表，先建出 $1$~MXN 的所有階乘模逆元則是根據建好的階乘表，先快速冪算出 inverse($n!$)，而 inverse$((n-1)!)$ 即為 inverse($n!$) $\cdot$ $n$ ```cpp= #define MXN 1'000'005 #define N 1'000'000 #define ll long long ll fac[MXN], inv[MXN]; fac[0] = 1; // 0! = 1 for(int i = 1; i <= N; i++) fac[i] = fac[i-1] * i % mod; inv[N] = fpow(fac[N], mod-2); // 快速冪 for(int i = N-1; i >=0; i--) inv[i] = inv[i+1] * (i+1) % mod; ``` ```cpp= ll C(int n,int k){ return fac[n]*inv[k]%mod*inv[n-k]%mod; } ``` 因此可以在 $O(N + \log p)$ 的時間建出所有 $\le N$ 的階乘與模逆元 ##### (當然 MXN 太大不要強制建表，會TLE，要注意題目給的值域) ---- 假如前面已經建好了階乘表，可以直接用 $O(1)$ 算出階乘表範圍內某個數字 $a!$ 的逆元！ ``` inv[a] ``` 如果這時需要一個數字 $a$ 的逆元，也就是 $a^{-1}$ 可以用 inverse($a!$) $\cdot$ fac[$a-1$] = $\frac{1}{a!} \cdot (a-1)! = a^{-1}$ 求出 ```cpp! inv[a] * fac[a-1] % mod; ``` --- ## 錯排公式給一個 $1\sim n$ 的排列，求出第 $i$ 個元素不在位置 $i$ 的方法數以 n = 4 為例，有 9 種方法 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321 ---- ## 公式設 $D_n$ 為長度為 $n$ 錯排方法數 $D_1 = 0$ $D_2 = 1$ $D_n = (n-1) (D_{n-1} + D_{n-2})$ 假設有 $n$ 個元素，一開始是排列 $1\sim n$ 為了讓每個元素不能在同一個位置，每次選一個後面的元素交換從第一個元素開始，後面有 $n-1$ 元素可以交換，因此乘上 (n-1) ---- $D_n = (n-1) (D_{n-1} + D_{n-2})$ 換過去之後，有兩種選擇 1. 換過去的第一個元素後面不能選，剩下 n-2 個元素要處理 2. 換過去的第一個元素後面可以選，則剩下 n-1 個元素要處理因此可以 $O(N)$ 求出錯排公式 --- ## 卡塔蘭數 ![image](https://hackmd.io/_uploads/ryhGYA-6yl.png) ---- ## 卡塔蘭數在組合數學中常見的的一種數列如以下都是卡塔蘭數: - $n$ 對括號的合法匹配數量 - $n\times n$ 的格點，從左下到右上，不能越過對角線的最短路徑個數第0項到第5項的卡塔蘭數為 1, 1, 2, 5, 14, 42 ---- ## 公式以 $n$ 對括號的合法匹配數量為例 $C_i$ 為 $i$ 對括號合法匹配數量，也代表卡塔蘭數 $C_0 = 1$ $C_{n+1} = \sum\limits_{i=0}^{n}{C_iC_{n-i}}$ for $n \ge 0$ 0 對括號的方法數為 1 種而 ${n+1}$ 對的方法數為假設當前放一對括號，剩下的 $n$ 對其中 $i$ 對放在當前括號中，剩下的 $n-i$ 對放在當前括號後面的方法數 ---- ## 公式(遞迴式) $C_0 = 1$ $C_{n+1} = \sum\limits_{i=0}^{n}{C_iC_{n-i}}$ for $n \ge 0$ 而轉換後等於 $C_{n+1} = \frac{2(2n+1)}{n+2} C_n$ 可以 $O(N)$ 算出來 ---- ## 公式(一般式) 透過一些關於生成函數的[證明](https://oi-wiki.org/math/combinatorics/catalan/#%E5%B0%81%E9%97%AD%E5%BD%A2%E5%BC%8F)，可以得出一般式 $C_0 = 1$ $C_1 = 1$ $C_n = \frac{1}{n+1} \cdot \binom{2n}{n} = \binom{2n}{n}-\binom{2n}{n-1}$ 砸組合數就可以 $O(1)$ 得出 $C_n$ ##### ~~講師不會[證明](https://oi-wiki.org/math/combinatorics/catalan/#%E5%B0%81%E9%97%AD%E5%BD%A2%E5%BC%8F)，所以簡單帶過~~ --- # 中堂下課 :dove_of_peace: --- ## 排容定理 (容斥原理) ![image](https://hackmd.io/_uploads/SyYrFAbpye.png =400x) ---- 如果我們使用$A , B , C$ 去代表三個集合，則元素總個數會是 $|A \cup B \cup C|$ 那如果我們要計算這個，則需要扣除重複的部分，也就是$|A \cap B| , |B \cap C| , |C \cap A|$ 那會發現我們又不小心多刪除了，於是需要加回$|A \cap B \cap C|$ 也就是 $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$ ![](https://i.imgur.com/krlh19T.png =500x) ---- 在 $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|$ 一個集合減去兩個集合的交集加上三個集合的交集 ... 直到算出所有可能的交集為止。 ---- ## 例題 [CSES 2185. Prime Multiples](https://cses.fi/problemset/task/2185) 給你數字 $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 ---- 範例程式碼 ```cpp for (int s = 1; s < 1<<n; s++) { int sign = -1; if (__builtin_popcount(s)&1) sign = 1; int mul = 1; for (int j = 0; j < n; j++) { if (s & (1<<j)) { mul = mul * a[j]; } } ans += sign * (n / mul); } ``` --- ## 輾轉相除法 ![image](https://hackmd.io/_uploads/SJD29R-T1e.png =500x) ---- 計算兩個數字 $a$ , $b$ 的最大公因數 $gcd(a,b)$ 同時在程式實作裡，我們會使用輾轉相除法進行實作。即 $gcd(a,b)=gcd(b,a \ mod \ b)$ $a$ , $b$ 非負且 $a\ge b$ 輾轉相除法求解最大公因數並不是唯一方法，但相當快速。 ---- 輾轉相除法 be like: ![image](https://hackmd.io/_uploads/SkfswCb61e.png) ---- ## 具體實作 ```cpp int gcd(int a, int b) { int r = a % b; while (r != 0) { a = b; b = r; r = a % b; } return b; } ``` 那其實也可以寫成 ```cpp int gcd(int a,int b) { return b == 0 ? a : gcd(b,a % b); } ``` ---- 當然也可以直接呼叫預設函式 since C++14 ```cpp #include<algorithm> __gcd(a,b); ``` since C++17 ```cpp #include<numeric> gcd(a,b); ``` --- ## 拓展歐幾里得--EXGCD ![image](https://hackmd.io/_uploads/rJSxjCZ6yx.png) ---- ## 裴蜀定理對於二元一次 $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$，$ax_1 + by_1 = gcd(a,b)$ $bx_2 + (a$ mod $b)y_2 = gcd(b,a$ mod $b)$ 根據輾轉相除法得 $gcd(a,b) = gcd(b,a$ mod $b)$ 所以 $ax_1 + by_1 = bx_2 + (a$ mod $b)y_2$ 又因為 $a$ mod $b = a - (\lfloor \frac{a}{b} \rfloor \times b)$ 所以 $ax_1 + by_1 = bx_2 + (a - (\lfloor \frac{a}{b} \rfloor \times b)) y_2$ $ax_1 + by_1 = ay_2 + bx_2 - \lfloor \frac{a}{b} \rfloor \times by_2$ $ax_1 + by_1 = ay_2 + b(x_2 - \lfloor \frac{a}{b} \rfloor y_2)$ 上個式子可以知道 $( x_1 = y_2, y_1 = x_2 - \lfloor \frac{a}{b} \rfloor y_2 )$ 將$( x_2, y_2)$ 不斷帶入遞迴求解，直到$gcd(a,b)=0$，這時就可以把 $x=1,y=0$ 遞迴回去求解了 :D ---- 模板： ```cpp! #define ll long long int extgcd(int a, int b, ll &x, ll &y) { if(b == 0){ x = 1; y = 0; return a; } int GCD=extgcd(b, a%b, y, x); y -= a / b * x; return GCD; } int main(){ int a, b, x, y; cin >> a >> b; int GCD = extgcd(a, b, x, y); } ``` 丟 $a,b,x,y$ 進去，可以得到 $a$ 和 $b$ 的$gcd$，並且把 $ax+by=gcd(a,b)$ 的一組解存進 $(x,y)$ ---- extgcd 除了解二元一次還可以用來求逆元，可以把同餘的式子轉化為二元一次方程式！ $ax \equiv 1$ mod $p$ $\rightarrow ax + py =1$ 直接把 $a,x,p,y$ 丟進模板即可 :D ---- ## Problem ### [NCPC 2020 初賽](https://ncpc.ntnu.edu.tw/file/109/%E5%88%9D%E8%B3%BD-109.pdf) ![](https://i.imgur.com/ZdpNDFo.png) ---- $t$ 筆測資，每筆給 $p,q,r$ 滿足式子的 $x,y$ 中，$\vert x\vert + \vert y\vert$ 最小可以是多少 ``` input 3 2 3 5 4 4 3 13 5 7 output 2 1 5 ``` ---- 只需要移項完式子後使用三分搜搜索 $x$ 及 $y$ 即可，會發現他的 $x$ 值以及 $y$ 值的圖形是為一個斜線(直線)，所以只需要使用三分搜查詢到那兩個點，就可以確定答案。 --- ## [題單](https://vjudge.net/contest/702336) ![image](https://hackmd.io/_uploads/HyR_iKM6kl.png)