数论
欧拉函数：
$\varphi(n)$ 表示 $[1,n]$ 中和 $n$ 互质的数的个数。
欧拉函数的计算：
公式计算：
$\varphi(n)=n\times(1-\frac{1}{p_1})\times…\times(1-\frac{1}{p_m})$，其中 $p_1,…,p_m$ 是 $n$ 的质因子。
时间复杂度同质因数分解。
通过 $\varphi(n)$ 得到 $\varphi(d),d\mid n$：
若得到了 $\varphi(n)$，可以通过 dfs 枚举质因数指数，$O(\sqrt n)$ 得到所有 $\varphi(d),d\mid n$。
筛法计算：
等价于筛法求积性函数。
$\varphi(i\times p)=\varphi(i)\times p,p\mid i$，$\varphi(i\times p)=\varphi(i)\times \varphi(p),p\not\mid i$。
特殊地，$\varphi(p)=p-1$。
欧拉定理：
$\gcd(a,p)=1,a^{\varphi(p)}\equiv 1\pmod p$。
扩展欧拉定理：
$a^b\equiv\begin{cases}a^{b\bmod\varphi(p)}&\gcd(a,p)=1\a^b&\gcd(a,p)\neq1,b\leq\varphi(p)\a^{b\bmod \varphi(p)+\varphi(p)}&\gcd(a,p)\neq1,b\geq\varphi(p)\end{cases}\pmod p$
欧拉降幂：
求 $a^{2^{2^{2^{2^{.^{.^.}}}}}}\bmod p$。
运用扩展欧拉定理不断对指数递归 $\bmod \varphi(p)+\varphi(p)$ 即可。
欧拉降幂是扩展欧拉定理的一个特殊情况，其核心是：$\varphi(\varphi(\varphi(…)))$ 不断递归后，大约在 $\log n$ 次后到 $1$。
群论：
群是有运算和变换方法的集合，写作 $(G,\cdot)$。$G$ 表示元素集合，$\cdot$ 表示运算。
一个群要满足下面四个性质：
- 封闭性：对于所有 $a,b\in G$，$a\cdot b\in G$。
- 结合律：对于所有 $a,b,c\in G$，$(a\cdot b)\cdot c=a\cdot(b\cdot c)$。
- 单位元：$G$ 中存在唯一一个 $e$，满足对于所有 $a\in G,a\cdot e=e\cdot a=a$。
- 逆元：对于所有 $a\in G$，总存在一个元素 $b$（可以 $b=a$），使得 $a\cdot b=b\cdot a=e$，称 $b$ 为 $a$ 的逆元，写作 $a^{-1}$。可以发现，实际上 $a,b$ 互为逆元。
模意义下的乘法群：
同余定理：
$a+b\equiv (a\bmod p)+(b\bmod p)\pmod p$
$a\times b\equiv (a\bmod p)\times (b\bmod p)\pmod p$
- 封闭性：$a\in G,b\in G,a\times b\equiv ab\in G$。
- 结合律：$a\times b\equiv b\times a$。
- 单位元：$a\times 1\equiv 1\times a$。
逆元：
逆元：$ab\equiv 1$。
此时，逆元没有那么显然。甚至不那么确定是否一定存在逆元。
考虑同余方程 $ax\equiv 1\pmod p$，此方程有解，当且仅当 $\gcd(a,p)\mid 1$，即 $\gcd(a,p)=1$。
所以对于一个固定的模数 $p$，只有 $\gcd(a,p)=1$ 的 $a\in G$。
求逆元：
对于一般存在的逆元，使用 exgcd 解同余方程即可。
对于模数为质数的逆元，使用费马小定理结合快速幂即可。
时间复杂度：$O(\log p)$。
线性预处理逆元：
求 $a_1,…,a_n$ 每个数的逆元。
令 $f(n)\equiv\prod\limits_{i=1}^n a_i$，$g(n)=f(n)^{-1}$。
$O(n)$ 即可预处理 $f(i)$。
而 $g(n)=f(n)^{-1}$，单次 $O(\log n)$ 即可求得。
$g(i)$ 根据 $g(i-1)=g(i)\times a_i$，从 $g(n)$ 递推即可。
总时间复杂度：$O(n)$。
阶：
满足 $a^r\equiv 1\pmod n$ 的最小正整数 $r$，称为 $a$ 模 $n$ 的阶，要求 $\gcd(a,n)=1$。记作 $\delta_n(a)=r$
性质：
- $a^1,…,a^r \bmod n$ 的结果两两不同。
- 若 $a^i\equiv a^j\pmod n(0\leq i,j)$，则 $i\equiv j\pmod r$。
原根：
若 $\delta_n(a)=\varphi(n)$，则称 $a$ 是 $n$ 的原根。原根一般写作 $g$。
原根存在定理：
只有 $2,4,p^a,2p^a$，其中 $p$ 是大于 $2$ 的质数，$a$ 是正整数。
离散对数：
模数为质数时，$\varphi(p)=p-1$，对于 $g^i\equiv a\pmod p$，在 $i\in [1,p-1]$ 时 $a\in [1,p-1]$，因此 $i$ 和 $a$ 恰好一一对应。此时的 $\varphi(p)$ 同时也是阶。
因此 $g^i\equiv g^j\pmod p\rightarrow i\equiv j\pmod {p-1}$。
$g^i\times g^j\equiv g^{(i+j)\bmod p-1}\bmod p$
形式化地，$\prod g^{a_i}\equiv g^{\sum a_i\bmod p-1}\pmod p$。
观察到，这和整数对数的形式是一致的。
所以称 $g^i\equiv a\pmod p$ 的 $i$ 为 $a$ 的离散对数，模数的原根不唯一，因此根据不同的 $g$，可得 $a$ 不同的离散对数 $i$。通常写作 $\text{ind}_ga$。
形式化地，$\text{ind}_ga+\text{ind}_gb=\text{ind}_gab,\text{ind}_ga-\text{ind}_gb=\text{ind}_g{\frac{a}{b}},\text{ind}_ga^k=k\text{ind}_ga$。
应用：
在 NTT 做乘法卷积时，可以通过原根求离散对数转换成求离散对数的加法卷积。