<style> .reveal .slides { text-align: left; font-size:28px; } </style> # Number Theory ---- - 模逆元 - 組合數 - 排容原理 - 卡塔蘭數 - 錯排公式 - sieve 篩法技巧 - 數論分塊 - 歐拉函數 --- ## 模空間運算 整數在模空間底下計算，要讓計算結果在 [0, m-1] 之間 加減乘可以直接做，但除法會爛掉 $(a + b) \mod m = (a+b)\ \%\ m$ $(a - b) \mod m = ((a-b)\ \%\ m + m)\ \%\ m$ $(a \times b) \mod m = (a*b)\ \%\ m$ $(a\ /\ b) \mod m =\ ?$ ---- ## Modular multiplicative inverse ### 模逆元 $b \cdot b^{-1}\equiv 1\ (\mod m)$ 我們稱 $b^{-1}$ 為 $b$ 的模逆元 因此對於 $(a\ /\ b) \mod m$ 如果找到 b 的模逆元就可以把除法運算改成乘法了 $(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 > 1) 的情況下模逆元不存在 ---- 因此在 $b$ 與 $m$ 互質的情況下 要求出 a / b 可以求出 $(a\ /\ b) \equiv (a\ \times\ b^{m-2}) \mod m$ 而 $b^{m-2}$ 可以透過快速冪求出 通常需要取模的題目給的 $m$ 都會是很大的質數 ($10^9+7, 98244353$) 等 所以通常 $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$ 的階乘與模逆元 ```cpp= #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; ``` --- ## 排容原理 在 $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|$ 一個集合 減去 兩個集合的交集 加上 三個集合的交集 ... 直到算出所有可能的交集為止 複雜度為 $O(2^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 input N = 3, M = 15 質數為 {2, 5, 7} ### sample output 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 --- ## 卡塔蘭數 在組合數學中常見的的一種數列 如以下都是卡塔蘭數: - $n$ 對括號的合法匹配數量 - $2n+1$ 個節點所構成的二元樹，且每個節點只有0或2個子節點的個數 - $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)$ 算出來 --- ## 錯排公式 給一個 $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)$ 求出錯排公式 --- ## 質因數分解 每個數字質因數出現次數不超過 $lgN$ 個 (最多的情況是每個質因數都為 2) 如果題目需要多筆詢問，每次把數字 $x$ $(1 \le x\le 10^6)$ 質因數分解 ---- ## 質因數分解 則可以使用 sieve 篩法的概念，花 $O(NlglgN)$ 的時間，對於每個質數 $i$ 的倍數 $j$，紀錄 $i$ 為 $j$ 的質因數 ```cpp= int factor[MXN]; for(ll i = 2; i <= N; i++){ if(factor[i]) continue; for(ll j = i*i; j <= N; j+=i){ factor[j] = i; } } ``` 建完表之後，對於每次詢問整數 $x$ ， 不斷除以 factor[x] ，直到 x 本身也是質數為止。 ```cpp= map<int, int> factorization(int x){ map<int, int> prime; while(factor[x]){ prime[factor[x]]++; x /= factor[x]; } prime[x]++; return prime; } ``` 每次詢問複雜度為 $O(k)$，$k$ 為相異質因數數量 --- ## 數論分塊 在 $O(\sqrt{N})$ 的時間計算除法向下取整 $f(x)$ for $x = 1\sim N$ 的總和 直接來看經典例子 $\sum\limits_{i=1}^{N} (i \times \lfloor \frac{N}{i} \rfloor)$ 寫成程式碼即為 ```cpp= for(int i = 1; i <= n; i++){ sum += (i) * (n/i); } ``` ---- $\sum\limits_{i=1}^{N} i \times \lfloor \frac{N}{i} \rfloor$ 來看看 N = 10 $1 \times 10$, $\ 2 \times 5$, $\ 3 \times 3$, $\ 4 \times 2$, $\ 5 \times 2$, $\ 6 \times 1$, $\ 7 \times 1$, $\ 8 \times 1$, $\ 9 \times 1$, $\ 10 \times 1$ 可以分成兩部分 - $1 \times 10$, $\ 2 \times 5$, $\ 3 \times 3$ - $4 \times 2$, $\ 5 \times 2$, $\ 6 \times 1$, $\ 7 \times 1$, $\ 8 \times 1$, $\ 9 \times 1$, $\ 10 \times 1$ 前面的部分，被乘數 $\le \sqrt{N}$ 後面的部分，乘數 $< \sqrt{N}$ ---- 因此我們可以分兩部分做，兩部分複雜度都能在 $O(\sqrt{N})$ 做完 前面只需要暴力跑過去 $1\sim \sqrt{N}$ 所有數字計算答案 後者則計算乘數為 $1, 2,...,\sqrt{N}-1$ 包括的被乘數區間有多大 $4 \times 2$, $\ 5 \times 2$, $\ 6 \times 1$, $\ 7 \times 1$, $\ 8 \times 1$, $\ 9 \times 1$, $\ 10 \times 1$ 乘數為 1 包括的被乘數區間為 $(\frac{10}{2}+1)\sim 10$ 乘數為 2 包括的被乘數區間為 $(\frac{10}{3}+1)\sim \frac{10}{2}$ ... 以此類推 而被乘數的部分使用等差級數公式求和即可 這題類似例題可以寫 [UVa 11526. H(n)](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2521) --- ## 歐拉函數 $\varphi (N)$ 求出所有 $\le N$ $(1 \le N \le 10^{12})$ 的正整數有幾個跟 $N$ 互質 $\varphi(1) = 1$ $(1)$ $\varphi(8) = 4$ $(1, 3, 5, 7)$ ---- 分情況討論 1. $\varphi(1) = 1$ 2. $n$ 為質數，則 $n$ 與所有小於自己的正整數都互值 因此如果 $n$ 為質數，則 $\varphi(n) = n-1$ 3. $n$ 為質數的次方，即 $n = p^k$， $p$ 為任意質數 則 $\varphi(p^k) = p^k - p^{k-1} = p^{k}(1-\frac{1}{p})$ 與 $p^k$ 不互質的整數有 $1\times p, 2\times p,...,p^{k-1}\times p$，總共 $p^{k-1}$ 個 除了這些剩下都是互質的整數 4. $n = p\times q$，$p, q$ 分別為兩個互質的整數 則 $\varphi(n) = \varphi(p\times q) = \varphi(p)\times\varphi(q)$ ---- 而如果我們把整數 $N$ 質因數分解後變成 $N = P_1^{k_1} \times P_2^{k_2} \times P_3^{k_3}...$ 而根據 $\varphi(N) = \varphi(p\times q) = \varphi(p)\times\varphi(q)$ 則 $\varphi(N) = \varphi(P_1^{k_1}) \varphi(P_2^{k_2}) \varphi(P_3^{k_3})...$ 在根據第 3 條簡化 $\varphi(N) = p_1^{k_1}(1-\frac{1}{p_1})p_2^{k_2}(1-\frac{1}{p_2})p_3^{k_3}(1-\frac{1}{p_3})... = N (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})(1 - \frac{1}{p_2})$ ---- $\varphi(N) = N (1 - \frac{1}{p_1})(1 - \frac{1}{p_2})(1 - \frac{1}{p_2})$ 因此把 $N$ 的所有質因數求出來即可以算出小於等於自己的互質整數數量 --- ## Question Time and Practice [Homework Link](https://vjudge.net/contest/500523) [競賽加分表單](https://docs.google.com/forms/d/e/1FAIpQLSf3ybC98L5ivPk_uLzCKi0FeX7uGJtG1ShTzORl9tPHkWAXgg/viewform?usp=sf_link) 提交期限到 6/30 23:59 截止 ---- ## END 這學期很快的結束了，相信各位在過了整個學期應該磨光了對於一開始對於競賽程式的幻想與熱情。 如果對於這學期的課程與作業大部分也只是競賽的基礎，如果能在接下來的暑假好好的充實自己，把不熟的單元好好的複習並且花巨量的時間 (約每天 10 小時以上) 去刷題，則今年 10 月的 [NCPC全國大專程式設計競賽](https://ncpc.ntnu.edu.tw/) 理論上可以拿到佳作，並且 11,12 月的 [ICPC 國際大學生程式設計競賽](https://icpc2021.ntub.edu.tw/final-scoreboard/) 可以拿到銅牌以上，全部精熟可以銀牌以上 ---- ## 賽制 ### [NCPC全國大專程式設計競賽](https://ncpc.ntnu.edu.tw/) 分為初賽與決賽， - 10月1日 初賽 - 每校前六隊晉級決賽 - 10月15日 決賽 - 約前 30-40 為佳作，前 11 名有獎金(第1/2/3/4名分別有1/2/3/5隊) ### [ICPC 國際大學生程式設計競賽](https://icpc2021.ntub.edu.tw/final-scoreboard/) - [TOPC 預賽](https://topc2021.icpc.tw/) ICPC 區域賽由TOPC排名決定晉級順序，通常補到100隊左右 - ICPC 需要報名費，前幾隊教練會補助因此也會有隊伍限制，前1-2隊可以晉級[世界決賽](https://www.youtube.com/watch?v=5IrtE19r-UA) ---- 如果對於程式競賽的熱情還沒被磨光的話，接下來的暑假 每周會開始模擬賽 會 virtual 一場 ICPC 歷屆 賽後各隊好好花時間補題 如果比賽題目有特別的技巧會在額外花時間解說 可以的話建議暑假好好刷 CSES 題單，總共只有 300 題 雖然很硬但會讓你進步很多，如果一個人暫時刷不完，各隊可以分配每個人刷不同主題 其中建議 DP, Graph 一定要好好練，台灣比賽很常光這兩個主題就佔了一半以上的題數 ---- 接著我就要離開海大了 謝謝大家這學期好好的學習 希望競賽程式的風氣能夠繼續在系上傳下去 並且期望之後很快的大家能拿到海大第二面、第三面...更多的銀牌 甚至能打破之前的紀錄第 13/101 名 ---- 不過之後可能會繼續教 ? 有任何題目想問我也可以隨時密我 ---- 也請大家幫我填個回饋表單 https://docs.google.com/forms/d/e/1FAIpQLSeOjui7UfiqabqTcoKy4nN2EI36LFzYg9ddw-NPshvhQCYOQw/viewform?usp=sf_link 祝大家暑假快樂