都别催！！！等我有时间了例题和详细讲解都会补回来的！！！
7.29 数论基础
你不会不知道吧
首先，你要知道
\[a \equiv b \pmod p \]是什么意思。然后，
\[\dfrac{a}{d} \equiv \dfrac{b}{d} \pmod \dfrac{p}{d} \]也是成立的。
扩展欧几里得 - ExGCD
-
裴蜀定理：\(\forall a,b \in \mathbf{Z},\ \exists x,y, \text{ s.t. } ax+by=(a,b).\)
-
求解裴蜀定理的方程：扩展欧几里得。
-
将 \((a,b)\) 的问题转化为 \((b,a \bmod b)\) 的子问题。
-
以前我们都是手动
swap，其实可以直接动个小手脚：int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } int g=exgcd(b,a%b,y,x); return y-=a/b*x,g; } -
\(|x| \leq b,|y| \leq a.\)（所以在 \(a,b \leq 10^9\) 的时候
exgcd才不会爆int。）证明：
中国剩余定理 - CRT
Chinese Remainder Theorem，AKA CRT.
- 思路是将多个同余方程合并成一个。
乘法逆元
- 定义：\(a^{-1} \cdot a \equiv 1 \pmod p\)。
- 何时存在逆元：\((a,p)=1\)。
- 威尔逊定理：\(\forall p \text{ is a prime, } (p-1)! \equiv -1 \pmod p\)。
- 扩欧求逆元。
- 费马小定理：\(\forall p \text{ is a prime, } a \in \mathbf{Z} \setminus {0}, a^{p-1} \equiv 1 \pmod p\)。
- 欧拉定理：\(\forall (a,p)=1, a^{\varphi(p)} \equiv 1 \pmod p\)。
- 欧拉定理是费马小定理的推广，费马小定理是欧拉定理的特殊情况。
- 线性预处理序列逆元：线性求序列前缀积，费马小 / 欧拉 / 扩欧求最后一个前缀积逆元，向前逆推前缀积逆元，前缀积乘下一个前缀积逆元获得当前数逆元。
Lucas 定理
BSGS - Baby Step Giant Step
- 离散对数问题：求解 \(t\) 使得 \(a^t \equiv b \pmod p\)。（这相当于求 \(\bmod p\) 意义下的 \(\log_a b\)）
- exBSGS
原根
7.29 - 积性函数、筛法和莫比乌斯反演
lk！
质数筛
- 埃氏筛：\(O(n \cdot \sum \dfrac{1}{prime})=O(n \log \log n)\)
- 欧拉筛：即线性筛
积性函数
-
数论函数：\(f:\mathbf{N}_+ \to \mathbf{C}.\) 下文函数都指数论函数。
-
积性函数：\((\forall a \bot b)f(ab)=f(a)f(b)\) 的数论函数。
常见的积性函数
定义 \(n = \prod_{i=1}^c p_i^{k_i}\)。
-
\(\epsilon(n) = [n=1],\)
-
\(1(n)=1,\)
-
\(Id(n)=n,\)
-
\(d(n)=\sum_{d \mid n} 1,\)
-
\(\sigma(n)=\sum_{d \mid n} d,\)
-
\(\varphi(n)= \sum_{i=1}^n [ i \bot n],\)
-
\(\mu(n) = [ \max \{ k_i \} \leq 1] (-1)^c.\)
-
-
完全积性函数：\((\forall a,b)f(ab)=f(a)f(b)\) 的数论函数。
-
数论卷积：即狄利克雷卷积。定义两个函数 \(f(n),g(n)\) 的卷积 \(h(n)\) 为 \(h(n)= \sum _{d \mid n} f(d) g(\dfrac{n}{d})\)，记作 \(h=f*g\)。
常见积性函数的卷积
积性函数的卷积仍是积性函数。
-
\(\epsilon * f = f,\)
-
\(1 * 1 = d,\)
-
\(1 * Id = \sigma,\)
-
\(1 * \varphi = Id,\)
-
\(1 * \mu = \epsilon.\)
-
莫比乌斯反演
\[f(n)=\sum_{d \mid n} g(d) \implies g(n)=\sum_{d \mid n} f(d) \mu (\frac{n}{d}) \]\[f(n)=\sum_{n \mid d} g(d) \implies g(n)=\sum_{n \mid d} f(d) \mu (\frac{d}{n}), \]证明：
\[f = g * 1 \iff f * \mu = g * 1 * \mu = g * ( 1 * \mu ) = g. \]亦可认为 \(g(n)\) 变换如下：
\[\begin{aligned} g(n) & = \sum \limits_{d \mid n} \mu (\dfrac{n}{d}) f(d) \\ & = \sum \limits_{d \mid n} \sum \limits_{e \mid d} g(e) \mu (\dfrac{n}{d}) \cdot 1 (\dfrac{d}{e})\\ & = \sum \limits_{e} g(e) (1 * \mu) ( \dfrac{n}{e} ) \\ & = \sum \limits_{e} g(e) [ \dfrac{n}{e} = 1 ] \\ & = g(n). \end{aligned}\]