# 110 選手班 - 數學 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.13 --- ## Outline - Number Theory - Modular - Combinatorics - Matrix --- ## Number Theory ---- 數論是純粹數學的分支之一，主要研究整數的性質。被譽為「最純」的數學領域。 --wiki ---- ### Divisibility - $a$ 整除 $b$ - $\implies az = b,\ z \in \mathbb{Z}$ - $\implies a\mid b$ - $a$ 不整除 $b$ $\implies a \nmid b$ ---- - $N = ab$ - $\implies min(a,b) \leq \sqrt N$ ---- Proof - if $a,b > \sqrt N$ - $\implies ab > N \rightarrow\leftarrow$ ---- #### Uva 10976 - Fractions Again?! - Given integer $k\ (1 \leq k \leq 10^4)$ - Find all pairs $(x,y)\ S.T.$ - $x \leq y$ - $\frac{1}{x} + \frac{1}{y} = \frac{1}{k}$ ---- - $(x - k)(y - k) = k^2$ - $\because (x-k) < (y-k)$ - $\therefore (x-k) \leq \sqrt {k^2}$ - enumerate $(x-k) \in [1,k]$ - $O(k)$ ---- ### Prime Test - test numbers in $[1, \sqrt N]$ - Time complexity: $O(\sqrt N)$ ```c= bool isprime(int n) { for(int i=2; i*i <= n; ++i) if(n % i == 0) return false ; return true ; } ``` ---- #### Millar-Rabin - check a number $N$ is prime or not by calling $millerRabin(n, a)$ for all $a$ required. - If passed test, there is a 75% correct rate. - If failed test, $N$ is not a prime. ---- ```c= // n < 4,759,123,142 {3 : 2, 7, 61} // n < 1,122,004,669,633 {4 : 2, 13, 23, 1662803} // n < 3,474,749,660,383 {6 : primes <= 13} // n < 2^64 {7 : 2, 325, 9375, 28178, 450775, 9780504, 1795265022} bool millerRabin(ll n, ll a) { if (n < 2) return 0; if ((a = a%n) == 0) return 1; if (n & 1 ^ 1) return n == 2; ll tmp = (n - 1) / ((n - 1) & (1 - n)); ll t = log2((n - 1) & (1 - n)), x = 1; for (; tmp; tmp >>= 1, a = a*a%n) if (tmp & 1) x = x * a % n; if (x == 1 || x == n - 1) return 1; while (--t) if ((x = x*x%n) == n - 1) return 1; return 0; } ``` ---- ### Prime Factorization $N = p_1^{r_1}p_2^{r_2}p_3^{r_3}...$ - find all $p \in [2,\ \sqrt N]$, divide $N$ by $p$ - $p_i > \sqrt N$ ？ - remain $N'$ - Time Complexity: $O(\sqrt N)$ ---- ```c= void prime_factor(int n){ for(int i=2; i*i<=n; i++){ if(n%i == 0){ int cnt = 0; while(n%i == 0){ n /= i; cnt++; } cout << i << ' ' << cnt << endl; } } if(n>1) cout << n << ' ' << 1 << endl; } ``` ---- ### Sieve of Eratosthenes - 埃氏篩法 - Find all primes under $N$ - If $p$ is prime - $\implies 2p, 3p, 4p,...$ is not prime - $\implies p^2,\ p^2+p,\ p^2+2p,...$ ---- ```c= const int N = 10000 bool isprime[N+10]; void eratosthenes() { for(int i=2; i<=N; i++) isprime[i] = true; isprime[0] = isprime[1] = false; for(int i=2; i<=N; i++) if(isprime[i]) for(int j=i*i; j<=N; j+=i) isprime[j] = false; } ``` ---- #### Time Complexity - $\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + \frac{N}{7} + ...$ - $=O(N\ ln\ ln\ N)$ - Proof: IDK QQ - Keyword: Sum of reciprocals of primes ---- #### Linear Sieve - $O(N)$ - https://cp-algorithms.com/algebra/prime-sieve-linear.html ---- ### Prime Factorization 2.0 - $N$ at most $O(log\ N)$ prime factors - Find one every time - $isprime[i] :=$ prime factor of $i$ - $N = isprime[N] \times \frac{N}{isprime[N]}$ ---- ```c= #define N 1000000 int isprime[N+10]; void eratosthenes(){ for(int i=2; i<=N; i++) isprime[i] = 0; isprime[0] = isprime[1] = 0; for(int i=2; i*i<=N; i++) if(isprime[i] == 0) for(int j=i*2; j<=N; j+=i) isprime[j] = i; } void prime_factor(int n){ int cnt = 0, k = isprime[n]; while(isprime[n] != 0){ if(k != isprime[n]){ cout << k << ' ' << cnt << endl; cnt = 0; } k = isprime[n]; n /= isprime[n]; cnt++; } cout << n << ' ' << cnt+1 << endl; } ``` ---- #### Time Complexity - $N$: Integers not over $N$ - $Q$: $Q$ queries - $O(NloglogN + QlogN)$ ---- ### GCD 輾轉相除法 ```c= int gcd(int a, int b) { return a == 0 ? b : gcd(b, a % b)； } ``` ---- ### Bézout's theorem - 貝祖定理 - $a, b \in \mathbb{Z}$ - $\exists x,y \in \mathbb{Z}$ - $S.T. ax + by = \gcd(a,b)$ ---- ### EXT_GCD - Extended Euclidean algorithm - 擴展歐幾里得算法 - Find $ax + by = \gcd(a,b)$ ---- - $a = 0,\ b = k$ - $(x,y) = (0,1)$ - $\implies ax + by = \gcd(a,b)$ ---- - $\gcd(a,\ b) = \gcd(b,\ a \% b)$ - $gcd(a, b) = b \times x + (a \% b) \times y$ - $= b \times x + (a - \lfloor \frac{a}{b}\rfloor \times b) \times y$ - $= a \times (y) + b \times (x - \lfloor \frac{a}{b}\rfloor \times y)$ - $(x',\ y') = (y,\ x - \lfloor\frac{a}{b}\rfloor\times y)$ ---- - extgcd$(a, b, x, y)$ - return $\gcd(a, b)$ - get $ax + by = \gcd(a, b)$ - recursive ---- ```c= int extgcd(int a, int b, int &x, int &y){ // ax + by = gcd(a, b) if(b == 0) { x = 1; y = 0; return y; } int xp, yp; int ret = extgcd(b, a%b, xp, yp); // xp * b + ap * (a%b) = gcd(a, b) x = yp; y = xp - yp * (a / b); return ret; } ``` ---- - $ax + by = \gcd(a,\ b)$ - $a(x + kb) + b(y - ka) = \gcd(a,\ b)$ - $k \in \mathbb{Z}$ --- ## Modular ---- - 模運算 - 模除 - modulo / modulus ---- ### 同餘 - $a \equiv b \pmod m$ - $a$ 同餘於 $b$ 模 $m$ - $9 \equiv 1 \pmod 4$ - $9 \equiv -3 \pmod 4$ ---- - $a \equiv b \pmod m$ - $\Leftrightarrow m \mid (a - b)$ - $\Leftrightarrow a = b + mz\ (z \in \mathbb{Z})$ ---- Proof - $a \equiv b \pmod m,\ c \equiv d \pmod m \\\implies a+c \equiv b+d \pmod m$ - $a = b + m_1z, c = d + m_2z\\ \implies (a + c) = (b + d) + mz$ - $(a + c) = (b + d) + (m_1 + m_2)z = (b + d) + mz$ ---- - $(A + B) \% m = (A \% m + B \% m) \% m$ - $(A - B) \% m = (A \% m - B \% m + m) \% m$ - $(A \times B) \% m = ((A \% m) \times (B \% m)) \% m$ ---- - $a + b: \mod M$ - $a - b: \mod M$ - $a \times b: \mod M$ - $a \div b: \mod ...$ ？ ---- ### 模逆元 - $ax \equiv 1 \pmod m$ - $x$ 是 $a$ 模 $m$ 下的模逆元 - $x \equiv a^{-1} \pmod m$ ---- - $(a \div b) \pmod m$ - $\implies (a \times b^{-1}) \pmod m$ ---- ### Fermat's little theorem - 費馬小定理 - $a \in \mathbb{Z}, p$ is prime - $\implies a^p \equiv a \pmod p$ - $\implies a^{p-1} \equiv 1 \pmod p$ - $\implies a \times a^{p-2} \equiv 1 \pmod p$ - $\implies a^{p-2} \equiv a^{-1} \pmod p$ ---- #### Proof-1 - $1a, 2a, 3a, ..., (p-1)a \pmod p$ 不同餘 - If $xa \equiv ya \pmod p,\ (x,y \leq p-1)$ - $\implies p \mid (x-y)a$ - $\implies p \mid (x-y)$ or $p \mid a$ ---- - $(p-1)!a^{p-1} \equiv (p-1)! \pmod p$ - $a^{p-1} \equiv 1 \pmod p$ (消去定理) ---- #### Proof-2 - $(b+1)^p \equiv \binom{p}{p} b^p + \binom{p}{p-1} b^{p-1} + ... \binom{p}{0} b^0 \pmod p$ - $\equiv \binom{p}{p} b^p + \binom{p}{0} b^0$ - $\equiv b^p + 1 \pmod p$ ---- - $(b+1)^p \equiv b^p + 1 \pmod p$ - $\equiv (b-1)^p + 1 + 1 \pmod p$ - $\equiv (b-2)^p + 1 + 1 + 1 \pmod p$ - ... - $\equiv {\begin{matrix}\underbrace {1+1+\dots +1+1} \\b+1\end{matrix}}{\pmod {p}}$ - $\equiv b+1 \pmod p$ - let $a = b+1 \implies a^p = a \pmod p$ ---- Key - mod $P$, $P$ is prime - $\div a \rightarrow \times a^{p-2}$ - (快速冪) ---- ### EXT_GCD - $ax + by = \gcd(a,b)$ - Find $ax = 1 \pmod p$ - $\implies ax - 1 = pz$ - $\implies ax - pz = 1$ - $\implies ax + pz = gcd(a,p)$ ---- ### Linear Congruence - 線性同餘方程 - $ax \equiv b \pmod p$ ---- - $ax \equiv b \pmod p$ - $\implies ax - b = pz$ - $\implies ax - pz = b$ - let $k = \frac{b}{\gcd(a,p)}$ - $\implies ax'k + pz'k = \gcd(a,b) \times k = b$ ---- - $\gcd(a,b) \nmid b \rightarrow$ no solution - $\gcd(a,b) \mid b \rightarrow$ ext_gcd find $x',\ z'$ ---- ```c= int extgcd(int x, int y, int &a, int &b){ // ax + by = gcd(x, y) if(y == 0) { a = 1; b = 0; return x; } int ap, bp; int ret = extgcd(y, x%y, ap, bp); // ap * y + bp * (x%y) = gcd(x, y) a = bp; b = ap - bp * (x / y); return ret; } void solve(){ int a, b, n; // ax = b (mod n) cin >> a >> b >> n; int r, k, g; g = extgcd(a, n, r, k); // ra + kn = g -> ra = g (mod n) if(b % g) { cout << "No Solution" << endl; return ; } else { int ans = ( b / g * r ) % n; // a * (r * b/g) = g * b/g (mod n) if(ans < n) ans += n; cout << ans << endl; } } ``` ---- ### Chinese Remainder Theorem - 中國剩餘定理 - 韓信點兵、孫子定理 - 一元線性同餘方程組 ---- 「有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？」 - $x \equiv 2 \pmod 3$ - $x \equiv 3 \pmod 5$ - $x \equiv 2 \pmod 7$ ---- $m_1,\dots,m_k$ 兩兩互質，則 $\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \cdots \\ x\equiv a_k\pmod {m_k} \end{cases}$ 在 $\bmod m=m_1m_2\cdots m_k$ 下有唯一解 ---- - $M = m_1 \times m_2 \times\dots\times m_k$ - $M_i = \frac{M}{m_i}$ - $t_i \equiv M_i^{-1} \pmod {m_i}$ - $x = a_1t_1M_1 + a_2t_2M_2 + \dots +a_kt_kM_k$ ---- \begin{equation} \left. \begin{cases} x\equiv 23{\pmod {84}}\\ x\equiv 7{\pmod {160}}\\ x\equiv 2{\pmod {63}} \end{cases} \right. \Rightarrow \left. \begin{cases} x\equiv 7{\pmod {2^{5}}}\\ x\equiv 2{\pmod {3^{2}}}\\ x\equiv 7{\pmod {5}}\\ x\equiv 23{\pmod {7}} \end{cases} \right. \end{equation} ---- ### Euler Function - 歐拉函數 - $\varphi (n) := \{a\in[1,n]\mid\gcd(a,n)=1\}$ - $n=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$ - $\varphi(n) = \displaystyle n (\frac{p_1-1}{p_1})(\frac{p_2-1}{p_2})\dots(\frac{p_k-1}{p_k})$ ---- ```c= int phi(int n) { int ans = n; for(int i=2; i*i <= n; ++i) { if(n % i == 0) { ans = ans / i * (i - 1) ; while(n % i == 0) n /= i ; } } if(n > 1) ans = ans / n * (n - 1) ; } ``` ---- ### Euler's theorem - 歐拉定理 - $a^{\varphi(n)} \equiv 1 \pmod n$ - $a \times a^{\varphi(n) - 1} \equiv 1 \pmod n$ - $a^{\varphi(n) - 1} \equiv a^{-1} \pmod n$ ---- - if $n$ is prime: - $\implies a^{\varphi(n)} \equiv 1 \pmod n$ - $\implies a^{n-1} \equiv 1 \pmod n$ - $\implies$ 費馬小定理 --- ## Combinatorics ---- $C^n_m = \frac{n!}{m!(n-m)!}$ 對 $k!$ 跟 $(k!)^{P-2},\ (k \in [1,N])$ 建表 - 建表 $O(NlogP)$ - 查詢 $O(1)$ ---- $C^n_m = C^{n-1}_m + C^{n-1}_{m-1}$ DP求所有 $C^i_j,\ (i,j \in [1,N])$ 令 $dp[i][j] = C^i_j$ 則 $dp[i][j] = dp[i-1][j] + dp[i-1][j-1]$ - 建表 $O(N^2)$ - 查詢 $O(1)$ ---- ```c= #define N 100 int dp[N+10][N+10]; void init(){ dp[0][0] = 1; for(int i=1; i<=N; i++) for(int j=0; j<=i; j++) if(j == 0) dp[i][j] = 1; else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } ``` ---- - 法一 - 快速 - 若無模逆元則無法使用 - 法二 - 較慢 - 無需使用模逆元 --- ## Matrix ---- ### 矩陣相乘 - 三層迴圈實做 - Time complexity：$O(N^3)$ - $i,\ k,\ j$ order ---- ### 矩陣快速冪 費氏數列：$f(n) = f(n-1) + f(n-2)$ 求 $f(n), n \leq 10^{18}$ - Naive：$O(n)$ - 一般項：$F_n = \frac{[(\frac{1+\sqrt5}{2})^n - (\frac{1-\sqrt 5}{2})^n ]}{\sqrt 5} \Rightarrow$ $O($wtf$)$ - ??? ---- - $f(n+1) = f(n) + f(n-1)$ - $f(n) = f(n)$ ---- - $f(n+1) = 1\times f(n) + 1\times f(n-1)$ - $f(n) \ \ \ \ \ \ \ = 1\times f(n) + 0\times f(n-1)$ $$ \left[ \begin{matrix} f(n+1) \\ f(n) \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} f(n)\\ f(n-1) \end{matrix} \right] $$ ---- $$ \left[ \begin{matrix} f(n+2) \\ f(n+1) \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} f(n)\\ f(n-1) \end{matrix} \right] $$ $$ \left[ \begin{matrix} f(n+3) \\ f(n+2) \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} f(n)\\ f(n-1) \end{matrix} \right] $$ $\dots$ ---- $$ \left[ \begin{matrix} f(n) \\ f(n-1) \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right] ^ {n-1} \left[ \begin{matrix} f(1)\\ f(0) \end{matrix} \right] $$ 套用矩陣快速冪 $O(logN)$ ---- 線性遞迴 $f(n) = a\times f(n-1) + b\times f(n-2)$ ---- $$ \left[ \begin{matrix} f(n+1) \\ f(n) \end{matrix} \right] = \left[ \begin{matrix} a & b\\ 1 & 0 \end{matrix} \right] \left[ \begin{matrix} f(n)\\ f(n-1) \end{matrix} \right] $$ $$ \left[ \begin{matrix} f(n) \\ f(n-1) \end{matrix} \right] = \left[ \begin{matrix} a & b\\ 1 & 0 \end{matrix} \right]^{n-2} \left[ \begin{matrix} f(2)\\ f(1) \end{matrix} \right] $$ --- ## (Hyper) Advance - 線性代數 - 生成函數 - 莫比烏斯反演 - 原根 - 群 - 快速傅立葉轉換 ---- ### GOOD STUFF Math Has a Fatal Flaw - Veritasium https://www.youtube.com/watch?v=HeQX2HjkcNo --- ## Credit - wiki - 2019 IONC - 2020 IOIC