<style> .reveal .slides { text-align: left; font-size:30px } </style> # Math --- * Miller Rabin * Pollard Rho * DiscreteSqrt * FFT * Josephus Queries * 歐拉函數 * $a^{b^c}$ --- 先備知識 : 若是數字太大，但是在 $-2^{127}$ ~ $2^{127}$ 的範圍，可以轉為使用 \_\_int128 來進行計算 而若輸出輸入需要，則有兩種處理方式 1. 快讀快出(推薦) 2. 字串處理 --- ## Miller Rabin ---- ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/Miller_Rabin.cpp) 大家應該聽過這個算法很多次了，那他其實是一個隨機化的質數判定算法，而為何他會特別的出眾呢?因為他的複雜度只需要 $O(k log^3 n)$ -- $k$ 為底數數量 而他的引入需要透過兩個定理，分別是費馬小定理以及二次探索定理，那不重要，所以不講。只需要知道怎麼用就好。 ---- ## 用法 那因為他是一個隨機化的算法，所以它並不是百分百正確，而是機率正確，那錯誤要怎麼改正呢? 就是取決於你取用的底數，對於這個算法來說你選取誰去做底數是非常重要的 1. 在int範圍內 選取 $\{1,7,61\}$ 會使得這個算法百分百正確 2. 在以上的範圍，則寫在模板裡面，可以直接看模板用。 就是每次拿底數去跟 $n$ 做一些探索，使得可以快速分辨他是否為質數。 回傳 $Yes/ No$ 是否為質數。 ---- ## 用法 需要處理或是引入的函數 : $mul$ , 把底數寫進 magic[] 陣列裡面 , 以及定義 $s$ 的大小 ```cpp int c; cin>>c; if(miller_rabin(c)){ cout<<"prime\n"; } else{ cout<<"not_prime\n"; } ``` --- ## Pollard Rho ---- ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/pollardRho.cpp) 他的作用是，可以快速地找到一個整數的其中一個因數(所以質數不能用)，而核心也是隨機化算法。 複雜度為 $O(n^{( \frac 14)})$ 回傳一個整數為傳入 $n$ 的因數。 ---- 什麼題目都用的到，可以配合Miller Rabin一起使用，做到質因數在$\log n$時間內的分解。 ---- ## 用法 需要處理或是引入的函數 : $add$ , $mul$ ```cpp int c; cin>>c; cout<<pollard_rho(c); ``` Miller Rabin 和 pollard_rho 常常因為複雜度的關係會搭配著使用，是在許多高難度的數論題目都會用到的常見模板。 其中 add(x, y, p) 為 (x+y)%p mul(x, y, p) 為 (x*y)%p 要記得 $x+y$, $x\cdot y$ 會超過 long long，請使用 \_\_int128 計算 ---- ## 利用Pollard Rho找到所有的質因數 ```cpp #define i64 __int64 vector<i64> ret; void fact(i64 x) { if (miller_rabin(x)) { ret.push_back(x); return; } i64 f = pollard_rho(x); fact(f); fact(x/f); } ``` 對。直接加這個。 你的 $ret$ 就會是所有的質因數 而 $vector$ 去 sort 或是做任何操作就可以找到你想找的數字。 ---- ## [例題](https://www.luogu.com.cn/problem/P4718) 題意 : 詢問一個數字的最大質因數，若最大質因數為他本身，則直接輸出 "Prime" 題解 : 那既然我們有了上面的工具，我們就只要先使用 Miller Rabin 判斷他是否為質數，然後再使用 Pollard Rho 搭配 fact 去找出所有質數，然後 sort 找出最大的即可。 --- ## Discrete_Sqrt ---- ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/DiscreteSqrt.cpp) 解決 $x^2 \mod p = a$ 的算式問題，根據模板我們可以看到， $a$ 和 $p$ 就是傳進去的 $a$ 和 $p$ ，而 $x$ 和 $y$ 則是分別的兩種答案，因為會有 $x$ 和 $-(x)$ 兩種答案 這個模板的複雜度並沒有很重要，他就是專門拿來解決這個問題的通解，有遇到這種問題就砸這個 穩。 ---- ## [例題](https://www.acmicpc.net/problem/17603) 題意 : $t$ 筆測資，分別給出 $p , a_0 , a_1$ 求 $b_0 , b_1$，條件如下 : 1. $(b_0 \cdot b_1) \mod p = a_0$ 2. $(b_0 + b_1) \mod p = a_1$ 按照升序排列輸出 $b_0 , b_1$ 若沒有符合條件的答案則輸出 $-1 題解 : $\sqrt{(b_0 + b_1)^2 - 4 \cdot (b_0 \cdot b_1)}$ --- ## FFT ---- ## FFT 快速傅立葉變換 ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/FFT.cpp) 主要說白了就是很快的多項式乘法，給多項式 A 和 B 求出兩個多項式的乘積。 其中FFT算是數論裡愛出的題目，像是ICPC或者是之前校內賽的海洋盃都有出現，且很容易在各大賽場被重複包裝，算是數論的常客。 時間複雜度為 $O(n \log n)$ 原本樸素的暴力做法為 $O(n^2)$ 是有一定量級上的差距的 ---- ## 用法 在做所有事情之前，需要先跑一次 $pre\_fft$，而傳入的 $mul()$ 分別為 - 第一個多項式的長度 $\_n$, 第一個多項式 $a[\ ]$ - 第二個多項式的長度 $\_m$, 第二個多項式 $b[\ ]$ - 要儲存答案的陣列 $ans[\ ]$ 從頭到尾都不需要跑 $fft()$ 這個函式，讓他自己處理就好 記得 MXN 要設成 2 的冪次，設 $\ge$ 計算的長度的 2 的冪次 假設題目 n 最大為 10 ，乘法後會到 2*n，那 MXN 就要設成 32 (16太小) ---- ## [例題 1 :apple: and :banana: ](https://cses.fi/problemset/task/2111) 此題為 CSES 上的 FFT 入門 題意 : 你有 $n$ 個蘋果和 $m$ 個香蕉，他們的重量介於 $1$ 到 $k$ 之間，今天請你計算對於每個介於 $2$ ~ $2k$ 之間的重量 $w$ ，有幾種方式可以挑選一個蘋果和香蕉，使他們重量總重為$w$。(每顆重量最重為20000) 題解 : 那這題的重點是 $1 \leq a_i , b_i \leq 20000$ ，所以可以直接把重量變成次方，然後進行多項式乘法，就相當於次方的加法，最後輸出 $k$ ~ $2k$ 的次方的值即可。 ---- ## [例題 2 一個bit的位置](https://cses.fi/problemset/task/2112) 此題為CSES上的FFT入門 題意 : 給定一個二進制長度為 $n$ 的字串，計算每個為 $1$ 的 bit 的位置下標的差值，並在最後輸出。共有 $1$ ~ $n-1$ 個。 題解 : 你會發現，這題是要算差值，所以我們先把它改成次方丟進去，然後把其中一邊全部 $*(-1)$ 接下來跑去做FFT就會對了。 --- ## Josephus Queries ---- ## 約瑟夫問題 ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/Josephus.cpp) 應該是一個很常見的問題，其問題的複雜度也有非常非常多種，在這幾年也有各式各樣的進步，各式各樣的寫法，但依然沒有一種被公認最好的寫法或是最好的複雜度 而模板應該非常非常簡單，就是 $n$ 個人每 $m$ 次pick一個人，返回最後剩下來的人是誰。 ~~順帶一提 除非你要找出位置，否則請不要用linked list 去實作 很蠢~~ 而其中若是要求被踢出去的位置，會另外有非常多種寫法，就看每個人怎麼寫 ---- ## 線性時間內 它的核心就是，每次出局一個人，剩下 $n-1$ 個人，然後再加上一個相對位移 $k$ 去得到正確的答案，而此模板算法很明顯是 $O(n)$ ---- ## 對數 此種算法的核心是把 $n$ 壓掉，把問題面著重在每 $k$ 個人就有一個要get out的情況下的遞迴。時間複雜度為 $O(k \log n)$ ```cpp int josephus(int n, int k) { if (n == 1) return 0; if (k == 1) return n - 1; if (k > n) return (josephus(n - 1, k) + k) % n; int res = josephus(n - n / k, k); res -= n % k; if (res < 0) res += n; else res += res / (k - 1); return res; ``` ---- ## 例題 沒有例題，就是給大家知道一下 若題目詢問 第 $k$ 次出局的人是誰 ```cpp int ja(int N,int M,int i) { if(i==1) { return (M-1+N)%N; } return (ysfdg(N-1,M,i-1)+M)%N; } ``` 0-base 輸出離開隊列的順序 --- ## 歐拉函數 ---- ## 定義 $\phi (x)$ 為小於等於 $x$ 且和 $x$ 互質的數字個數，也就是 $\phi (1)=1$ 若 $x$ 為質數 則 $\phi (x)=x-1$ ---- ## 性質 (看過 有印象就好 1. 歐拉函數為積性函數 \*積性函數是指 若有 $gcd(a,b)=1$ 那 $\phi (a*b)=\phi(a)*\phi(b)$ 其中 若 $x$為奇數時，$\phi(2x)=\phi(x)$ 2. $n=\sum_{d \mid n} \phi(d)$ 3. 若$n=p^k$ ，且 $p$ 是質數的話，那 $\phi(n)=p^k-p^{k-1}$ 4. 由算術基本定理可知 $\phi(n)=n*\prod_{i=1}^s \frac {p_i-1}{p_i}$ 由第四點求出的通式$\phi(n)=x*\prod_{i=1}^n (1-\frac 1{p_i}))$ ---- 怎麼求歐拉函數 ```cpp int Euler(int n){ int now = n; for (int i = 2; i * i <= n; i++) if (n % i == 0){ now = now - now / i; while (n % i == 0) n = n / i; } if (n > 1) now = now - now / n; return now; } ``` ---- 那當然上面那個看起來很慢，所以我們會有更快的 : ```cpp int prime[10010], phi[10010]; bool v[10010]; void quick_euler(){ int cnt = 0; for(int i = 2; i <= N; ++i){ if(!v[i]) prime[++cnt] = i, phi[i] = i - 1; // 若 i 是質數，所以 φ(i) = i - 1 for(int j = 1; i * prime[j] <= N && j <= cnt; ++j){ v[i * prime[j]] = 1; if(i % prime[j] == 0){ phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } } ``` --- ## $a^{b^c}$ 這個有兩件事情值得講的 1. $(a^{b^c})(\mod m)$ 2. $a^{(b^c)}(\mod m)$ ---- ## $(a^{b^c})(\mod m)$ 好，首先這件事情，會想起於離散數學時學到的東西 $a^m \% m = 0$ $a^{m-1} \% m = 1$ $a^{m-2} \% m = a^{-1}$ 於是會發現這件事情 $a^b ≡ a^{(b \mod {m−1})} (\mod m)$ 所以同理可以推到C，於是就可以直接在紙上解開。 ---- 那如果今天遇到 $a^{b^c}(\mod m)$ 時要怎麼辦呢 ---- *歐拉函數 ${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}.}$ 首先，根據歐拉定理以及其函數的應用，可以知道 $A^{(B^C)} (\mod m) == A^{(B^C \mod (\phi(m) — 1))}(\mod m)$ 然後又因 $m$ 通常是一個大的質數，而若大家有記憶的話，歐拉函數時有提到，若 $m$為質數，則 $\phi(m)=m-1$ 於是又可以得知 $A^{(B^C \mod (m — 2))}(\mod m)$ 所以最後 $a^{b^c}(\mod m) = A^{(B^C \mod (m — 2))}(\mod m)$ --- 作業；