都别催！！！等我有时间了例题和详细讲解都会补回来的！！！

一些约定

• \(\mathbf{C}\)：复数集；
• \(\mathbf{Z}\)：整数集；
• \(\mathbf{N}\)：自然数集；
• \(\mathbf{N_+}\)：正整数集；
• \(\mathbf{P}\)：素数集；
• \(\forall\)：全称量词，即“对于所有的……”。“\(\forall x,p(x)\)”即“对于所有的 \(x,p(x)\) 成立。”
• \(\exists\)：存在量词，即“存在至少一个……”。“\(\exists x,p(x)\)”即“存在至少一个 \(x\)，使得 \(p(x)\) 成立。”
• \(\text{s.t.}\)：即 \(\text{subject to}\)，使得。

7.29 数论基础

你不会不知道吧

首先，你要知道

是什么意思。然后，

也是成立的。

扩展欧几里得 - 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 \in \mathbf{P}, (p-1)! \equiv -1 \pmod p\)。
• 扩欧求逆元。
• 费马小定理：\(\forall p \in \mathbf{P}, 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_k(n)=n^k,id_1\) 简记作 \(id\)（完全积性）；

  • 因子函数：\(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) \iff g(n)=\sum_{d \mid n} f(d) \mu (\frac{n}{d}) \]

  卷积形式：

  \[f = g * 1 \iff g = f * \mu \]

• 形式二

  \[f(n)=\sum_{n \mid d} g(d) \iff g(n)=\sum_{n \mid d} f(d) \mu (\frac{d}{n}), \]

\(\iff\) 两边分别为 莫比乌斯变换 和 莫比乌斯逆变换（反演）。

证明：

这里只给出形式一的证明 ，因为老师只讲了形式一。考虑在卷积形式下，将等式右边的 \(f\) 带入：

便干净利落地完成了证明。亦可认为 \(g(n)\) 变换如下：

积性函数前缀和

线性求 \(f(1) \sim f(n)\)

如果是积性函数，对于任何的 \(x\)，令 \(x = \prod_{i=1}^c p_i^{k_i}\)，其中 \(p_i \in \mathbf{P}\)，都有

所以，只要可以快速求出 \(f(p^k)\)，就可以在线性筛的过程中求出 \(f(x)\) 了。如 \(\varphi(x),\mu(x)\) 都可以被线性求出。

杜教筛

若要求 \(sum_{i=1}^n f(i)\)，可以找到容易计算前缀和的 \(g,s\) 使得 \(g * f = s\)，同时 \(g(1)=1\)，令 \(F,G,S\) 为 \(f,g,s\) 的前缀和，则有：