数论各篇参考（有几块在博客上被我拎出去单独成篇了）：
namomo summer camp 2021 吴航 数论
WC2016绵阳南山 宋新波 莫比乌斯反演
线性求逆元
$$
\lfloor\frac{p}{a}\rfloor\cdot a+(p\bmod a)=p\\
$$
推导可得
$$
\lfloor\frac{p}{a}\rfloor\cdot inv[p\bmod a]+inv[a] \equiv0\pmod{p}
$$
威尔逊定理
$$
(p-1)!\equiv -1\pmod p \Longleftrightarrow p\ is \ prime
$$
证明：
必要性：1至$p-1$这些数必然唯一对应其逆元，而每一对逆元相乘得1。因此只需考虑逆元是自己的元素，即$1$和$p-1$。显然结果为$-1$。
充分性：暂时不会 暂时没必要学
利用这个定理可以给出估计质数分布的式子
二次剩余(待学)
名字比较高大上。实际意义就是类似求模意义下的根号。
若p为奇素数，可用Cipolla算法
若p为奇素数的幂次，
若p为2，
其余情况，中国剩余定理
BSGS
基础
$$
a^x\equiv b\pmod m
\\给定a,b,m,其中\gcd(a,m)互质，求一个特解x
$$
首先由于欧拉定理，$a^{\varphi(m)}\equiv 1$。故找到某个$x$的特解后，$x+k\varphi(m)$都是方程的解。我们这里尝试找出小于$\varphi(m)$的一个$x$。
考虑将$x$设为$i\lceil \sqrt{\varphi(m)}\rceil-j$，则$i$在$[1,\lceil \sqrt{\varphi(m)}\rceil]$中取值，$j$在同样值域中取值，即可遍历所有$x$的取值。
记$\lceil \sqrt{\varphi(m)}\rceil$为$s$，则
$$
a^{si-j}\equiv b\pmod m\\
a^{si}\equiv b\cdot a^j\pmod m
$$
可以用根号时间枚举左式，根号时间枚举右式，利用unordered_map，即解决。
进阶
$$
x^a\equiv b \pmod p
$$
p为质数，求x。
找到所有解
积性函数
$k$表示质因子的数量，$e_i$表示第$i$个质因子的指数
欧拉函数$\varphi(n)=\prod _ { i=1 } ^ { k } p_i^{e_i-1}(p_i-1)$，1到n中与n互素的数的个数
约数个数函数$d(n)=\prod _ { i=1 } ^ { k } (e_i+1)$，n的约数个数。由于广义约数和函数的定义$\sigma_k(n)=\sum _ {d|n} d^k$，也被记作$\sigma_0(n)$。
约数和函数$\sigma(n)=\prod _ { i=1 } ^ { k } \sum _ { j=0 } ^ { e_i }p_i^j=\sum _ {d|n} d$，n的所有约数之和
莫比乌斯函数$\mu(n)=\prod _ { i=1 } ^ { k }(-\lfloor\frac{1}{e_i}\rfloor)$，若n有任何一个质因数大于1次，则0，若n为奇数个不同素数之积，则-1，否则1
完全积性函数
不需要a，b互质即成立$f(a)\cdot f(b)=f(a\cdot b)$
全1、全0函数（恒等函数）
单位元函数$\varepsilon(n)=(n==1)=\lfloor \frac{1}{n}\rfloor$
$f_a(x)=x^a$，a为常数，当a取1时是其中一个后面会用到的函数$id(x)=x$
欧拉函数的重要性质
$\varphi(n)=n\cdot \prod _ {i=1} ^ {m} (1-\frac{1}{p_i})$
其中$n=\prod _ {i=1} ^ {m} p_i^{e_i}$。根据欧拉函数的定义可得
$\varphi(p^k)=p^k-p^{k-1}$
由上一个式子，$\varphi(p^k)=p^k\cdot (1-\frac{1}{p})=p^k-p^{k-1}$
$n=\sum _ { d|n }\varphi(d)$
当$n=1$时，等式显然成立；
当$n$为质数时，$右式=\varphi(n)+\varphi(1)=n-1+1=n$，成立；
当$n$为质数的幂时，设$n=p^k$，$右式=\sum _ {i=0} ^ { k }\varphi(p^i)=\sum _ { i=1 } ^ {k}[p^{i}-p^{i-1}]+1=p^k=n$
当$n$为其它情况时，由于欧拉函数的积性，易证
$\sum _ {i=1} ^ {n} i\cdot[\gcd(n,i)=1]=\frac{\varphi(n)}{2}\cdot n(n>1)$
$(x,n)=1$时，$(n-x,n)=1$，因此每一对与n互质的数的和为n。共有$\frac{\varphi(n)}{2}$对。
同时可以得到下面的结论：
$n>2$时，$\varphi(n)$为偶数
其它积性函数的重要性质
$$
d(x\cdot y)=\sum _ {i|x} \sum _ {j|y} [\gcd(i,j)==1]
$$
证明的话 把某个质因数p列出来就发现它在左边的贡献和在右边是一样的
欧拉定理->扩展欧拉定理
$$
a^c\equiv
\begin{cases}
a^{c\ \bmod\ \phi(m)} &(a,m)\ =\ 1 \\
a^c &(a,m)\ \neq\ 1\ \land\ c\ <\ \varphi(m) \\
a^{c\ \bmod\ \phi(m)\ +\ \phi(m)} &(a,m)\ \neq\ 1\ \land\ c\ \geq\ \varphi(m)
\end{cases}
$$
杜教筛
用于求解积性函数前缀和，设$S$为$f$的前缀和
$$
狄利克雷卷积：\sum_{i=1}^n(f\ast g)(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac i d)\
=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}f(i)\
=\sum_{d=1}^ng(d)S(\lfloor\frac n d\rfloor)\
故\sum_{i=1}^n(f\ast g)(i)=\sum_{i=2}^n g(i)S(\lfloor\frac n d\rfloor)+g(1)S(n)\
g(1)S(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^n g(i)S(\lfloor\frac n d\rfloor)
$$
在具体例子中更好解释：
例题1
$$
求S(n)=\sum_{i=1}^n\mu(i)
$$
解
$$
设f(n)=\mu(n),g(n)=1(n),带入上式\
S(n)=\sum_{i=1}^n \varepsilon(i)-\sum_{i=2}^n S(\lfloor\frac n d\rfloor)\
=1-\sum_{i=2}^n S(\lfloor\frac n d\rfloor)
$$
即可记忆化递归处理。利用数论分块（整出分块），复杂度$O(n^\frac 3 4)$。
考虑较小的$S$不需要递归处理，可以线性预处理。经过数学证明可以找到$O(n^\frac 2 3)$这个平衡点，预处理前面这些、数论分块做后面这部分，总复杂度为$O(n^\frac 2 3)$。
为了应用杜教筛，显然莫比乌斯函数在很多情况下可以使式子中的某几项更容易计算。