<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 來進行計算 --- ## 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$ , 把底數寫進魔法數字裡面 , 以及定義 $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$ 的因數。 ---- 我也不知道要說甚麼。反正他什麼題目都用的到拉 ---- ## 用法 需要處理或是引入的函數 : $add$ , $mul$ , $\_\_gcd$ ```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 或者使用 [O(1) mul](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/O(1)mul.cpp) ---- ## 利用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$ 去做一些操作就可以找到最大的 ---- ## [例題](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)}$ --- ## 高斯消 ---- ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/gauss.cpp) 高斯消元法，應該大家都有在高中的時候學過，其中值得一提的是，當其用來解 xor方程組的時候，可以使用bitset優化。 時間複雜度為 $O(n^3)$ 那我們先教模板的用法(當然還有浮點數的用法)，在教更進階的轉換方式。 ---- ## 用法 需要處理或是引入的函數 : $ppow$ 快速冪 大家應該都記得，在解出 $x$ 個未知數的多項式時，就會需要 $x$ 條式子，而他就可以開出一個 $x *x$ 的增廣矩陣。 其中模板裡面的 ```cpp gs.v.resize(n , vector<int>(n + 1 , 0)); ``` 就是要記錄每一行的增廣矩陣。 而 $ans$ 的vector就是紀錄其中每個未知數依序的答案 就像是模板上寫的一樣，需要先 clear 然後再 resize x 的大小，就可以代入使用。 ---- ## xor in gauss 異或的方程組會長得像是下面這樣  一樣就只需要把參數記錄下來，直接跑就可以 而其中時間複雜度會降低成 $O(\frac {n^2m}{w})$ 但其實沒甚麼差。算過之後就會發現他只降低了一點點。 ```cpp bitset<1005> vector[n+1]; ``` ---- 理論上會長得像是這樣 ```cpp bitset<1010> matrix[2010]; //增廣矩陣 vector<bool> Gauss(int n, int m) { for (int i = 1; i <= n; i++) { int cur = i; while (cur <= m && !matrix[cur].test(i)) cur++; if (cur > m) return std::vector<bool>(0); if (cur != i) swap(matrix[cur], matrix[i]); for (int j = 1; j <= m; j++) if (i != j && matrix[j].test(i)) matrix[j] ^= matrix[i]; } std::vector<bool> ans(n + 1, 0); for (int i = 1; i <= n; i++) ans[i] = matrix[i].test(0); return ans; } ``` --- ## FFT ---- ## FFT 快速傅立葉變換 ## [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/math/FFT.cpp) 主要說白了就是很快的多項式乘法，根據模板上面寫的呢，我們只需要把第一個多項式填入 $a[\ ]$ 第二個多項式填入 $b[\ ]$ ，然後得出的 $ans[\ ]$ 就是乘法的答案。 其中FFT算是本日比較常用到的東西(應該是辣)，像是ICPC或者是之前校內賽的海洋盃都有出現，本週的作業其中一題就是海洋盃曾出過的題目。 時間複雜度為 $O(n lg n)$ 原本樸素的暴力做法為 $O(n^2)$ 是有一定量級上的差距的 ---- ## 用法 需要處理或是引入的函數 : 只有MAXN 在做所有事情之前，需要先跑一次 $pre_fft$，而傳入的 $mul()$ 分別為 第一個多項式的長度,第一個多項式,第二個多項式的長度,第二個多項式,答案陣列. 從頭到尾都不需要跑 $fft()$ 這個函式，讓他自己處理就好 ---- ## [例題 1 :apple: and :banana: ](https://cses.fi/problemset/task/2111) 此題為CSES上的FFT入門 題意 : 你有 $n$ 個蘋果和 $m$ 個香蕉，他們的重量介於 $1$ 到 $k$ 之間，今天請你計算對於每個介於 $2$ ~ $2k$ 之間的重量 $w$ ，有幾種方式可以挑選一個蘋果和香蕉，使他們重量總重為$w$。 題解 : 那這題的重點是 $1 \leq a_i , b_i \leq 100$ ，所以可以直接把重量變成次方，然後進行多項式乘法，就相當於次方的加法，最後輸出 $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 lg 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 輸出離開隊列的順序 --- ## $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)$ 那大家稍微動個腦應該就能直接解開了 ---- 那如果今天遇到 $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)$ --- ## [HW](https://vjudge.net/contest/572863) ## 可能可以...寫出 $\frac 23$ 喔...