<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Number Theory Introduction to Competitive Programming 3/15 --- * 質因數分解 * 鴿籠原理 :dove_of_peace: * 模運算 & 模逆元 * 歐幾里得算法(輾轉) * 拓展歐幾里得(求逆元，求方程解) * 中國剩餘定理(求方程解) * 排容定理(求聯集) --- ## 質因數分解 甚麼是質因數分解呢? 對於輸入一個整數 $N$ 可以找到他的所有質因數。 如果題目需要多筆詢問，每次把數字 $x$ $(1 \le x\le 10^6)$ 質因數分解，那會TLE 首先會發現因數是成對出現的，分布在$[ 2 , \sqrt{N} ]$ 和$[\sqrt{N}+1 , N)$，也就是說會需要遍歷$[ 2 , \sqrt{N} ]$ 也就是說複雜度為$O( \sqrt N)$ ---- 值得指出的是，如果開始已經打了一個質數表的話，時間復雜度將從$O(\sqrt N)$下降到 $O(\sqrt{\frac N {\ln N}})$。 只需遍歷每一個質數就可以去查詢出$N$的質因數。 ---- 然後考慮之前所教過的篩法，則可以使用 sieve 篩法的概念，花 $O(NlglgN)$ 的時間，對於每個質數 $i$ 的倍數 $j$，紀錄 $i$ 為 $j$ 的質因數 ```cpp= int factor[MXN]; for(long long i = 2; i <= N; i++){ if(factor[i]) continue; for(long long 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$ 為質因數數量 那這時候會發現，我們的質數表可以建立到 $10^6$ ，而質數表只需要建立到 $\sqrt N$ ，也就是說$10^6$的質數表受用範圍是可以求出 $10^{12}$ 內的質數 ---- 而如果只有一個數字要判斷是否為質數並不需要建質數表 直接從 2 開始跑到 $\sqrt{N}$ 為止，每次遇到有數字可以整除就是其中一個質因數 ```cpp map<long long, int> factorization(long long x){ map<long long, int> ret; for(long long i = 2; i*i <= x; i++){ if( x % i == 0){ ret[i]++; x /= i; while(x % i == 0){ x/=i; ret[i]++; } } } if(x > 1) ret[x]++; return ret; } ``` --- ## 鴿籠原理 ---- 亦稱抽屜原理。 常用於證明存在性證明(有兩個或以上)和求最壞情況(最差會有一個)下的解 經典問題就是鴿籠問題，若更為學術性則為將 $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$ 明顯不符。 ---- ## [實際應用在題目](https://vjudge.net/problem/UVA-11237) 關鍵點為製造抽屜(製造籠子) 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 =\ ?$ ---- ## [模逆元](https://atcoder.jp/contests/abc154/tasks/abc154_f) 發現除法會錯(也避免負數)之後，於是我們知道，需要 模 "逆元" ! 在模 $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)$ [證明參考](https://www.cnblogs.com/ac-evil/p/12680705.html) 於是就可以發現除法可以變成$(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$ 互質 --- # 下課 :bread: --- ## 歐幾里得算法 (輾轉) (GCD) ---- 計算兩個數字 $a$ , $b$ 的最大公因數 $gcd(a,b)$ 同時在程式實作裡，我們會使用輾轉相除法進行實作。 即 $gcd(a,b)=gcd(b,a \ mod \ b)$ $a$ , $b$ 非負且 $a\ge b$ 輾轉相除法求解最大公因數並不是唯一方法，但相當快速。 ---- ## 具體實作 ```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 ---- ## 裴蜀定理 對於不定方程$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$ ，方程才有整數解。 :brain: :fire: ---- ## 裴蜀定理在歐幾里得上的應用 於是，知道$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$ ```cpp 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$ 即可 ```cpp 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$ 值的圖形是為一個斜線(直線)，所以只需要使用三分搜查詢到那兩個點，就可以確定答案。 --- ## 中國剩餘定理 (Chinese Remainder Theorem, CRT) :bread: ---- 也是韓信點兵那些的經典例題，應該要對這些東西很熟悉 中國剩餘定理:設正整數 $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$ ---- ## 實作方式 會使用到模逆元，也就是會用到拓展歐幾里得 ```cpp #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 ``` ---- 跟範例程式碼差不多，只需要稍微確認輸入的順序，以及好好的初始化，然後套入程式碼即可。 --- ## 排容定理 (容斥原理) 如果我們使用$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|$ ---- 在 $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](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 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; } ```