数论（整数和他们的函数）、组合计数、线性代数、群论
gcd lcm 倍数 同余
bsgs：给定质数p，给定a和b，有(a,p)=1。求最小非负整数x，使得\(a^x\equiv b \pmod p\)
首先有欧拉定理，\(a^{\phi(p)}\equiv 1 \pmod p\)，当……p必须是质数，不是要用exbsgs
miller-rabin：快速判断一个数是否是素数
进行测试前只考虑奇数情况，有一个费马小定理的逆定理，对于任意素数p，\(\forall x\in [1,p-1]\)，都有\(x^p\equiv x\pmod p\)，而对于合数，这个等式不一定成立。有Camerial数如561也成立，但是是合数。
考虑\(x^2\equiv 1\pmod n\)的根，等价于\((x-1)(x+1)\equiv 0\pmod n\)，若n为奇素数则\((x-1)\)和\((x+1)\)中必定有一个为0，二次方程则最多有两个根，即为\(1\)和\(-1\)，若为奇合数则讨论变得复杂
二次探查……对于int32之内的数，a选取2,7,61即可；对于int64之内的数，选取前10个素数即可
pollard-rho：给定合数n，要对n质因数分解
随机基底a和c，生成序列\(x_0=a,x_i=x_{i-1}^2\)……生日悖论
线性筛
中国剩余定理：\[x\bmod p_1=x_1\\x\bmod p_1=x_1\\ \vdots\\ x\bmod p_n=x_n\]，求……
二次剩余：给定y和奇质数p，求x，使得\(x^2\equiv y\pmod p\)……
积性函数
数论函数：定义域在正整数上，值域一般在整数上的函数
狄利克雷卷积：\((fg)(n)=\sum_{d|n}f(d)g(\frac{n}{d})\)，枚举n的所有因子，两函数分别取值。如：\(fg[6]=f[1]\cdot g[6]+f[2]\cdot g[3]+f[3]\cdot g[2]+f[6]\cdot g[1]\)，暴力计算复杂度\(O(n\ln n)\)
积性函数：\(\forall(a,b)=1,f(ab)=f(a)\cdot f(b)\)，常见积性函数：
普通函数\[1(n)=1,id(n)=n,e(n)=[n=1]\]
除数函数\[\sigma_k(n)=\sum_{d|n}d^k\]
欧拉函数（1到n-1中和n互质数的个数）\[\phi(n)\]
莫比乌斯函数（如果n有质因子指数\(k_i\)大于2则为0，质因子个数\(m\)为奇数则为-1，偶数则为1）\[\mu(n)=[k_1\leq1][k_2\leq1]\cdots[k_m\leq1](-1)^m\]
积性函数的第一项一定为1，除了全是0的积性函数第一项可能是0
如果\(f,g\)是两个积性函数，那么他们的狄利克雷卷积\(h=fg\)也是积性函数：为了方便，n只有两个质因子，\(n=p_1^{k_1}p_2^{k_2}\)，交换求和号合并：
\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d})\\=\sum_{i_1=0}^{k_1}\sum_{i_2=0}^{k_2}f(p_1^{i_1}p_2^{i_2})g(p_1^{k_1-i_1}p_2^{k_2-i_2})\\=\sum_{i_1=0}^{k_1}\sum_{i_2=0}^{k_2}f(p_1^{i_1})f(p_2^{i_2})g(p_1^{k_1-i_1})g(p_2^{k_2-i_2})\\=\sum_{i_1=0}^{k_1}f(p_1^{i_1})f(p_2^{i_2})+\sum_{i_2=0}^{k_2}g(p_1^{k_1-i_1})g(p_2^{k_2-i_2})\\=h(p_1^{k_1})h(p_2^{k_2})\]
考虑把\(\mu\)和1卷起来来证：\[\sum_{d|n}\mu{d}=[n=1]\Rightarrow\mu*1=e\]
用欧拉函数的性质直接证：\[\sum_{d|n}\phi(d)=n\Rightarrow\phi*1=id\]
怎么求\(\phi,\mu\)的前n项？线性筛的同时将一个质数计算它筛到的数的函数值即可
怎么求\(\phi,\mu\)的前n项和？杜教筛之类的\(O(n^{\frac{2}{3}})\)
原根
给定n，若a满足$(a,n)=1$并且$1,a,a^2,\cdots,a^{\Phi(n)-1}$在$\bmod n$下都互不相同，则称a是n的一个原根。
$2,4,p^n,2p^n$有原根，其中$p$是奇素数；若$n$有原根，则原根的数量为$\phi(\phi(n))$个
组合数学
组合数：\(C^m_n=\frac{n!}{m!(n-m)!}\)，使用杨辉三角计算，也可以使用预处理阶乘和他的逆元
分块优化矩阵乘法递推
容斥原理
\(F(A\cup B\cup C)=F(A)+F(B)+F(C)-F(A\cap B)-F(A\cap C)-F(B\cap C)+F(A\cap B\cap C)\)
二项式反演
概率论
期望的线性性：求随机排列中逆序对的期望个数
\(E(x)=0\times P(x=0)+1\times P(x=1)+\cdots+n\times P(x=n)\)，并不好算，
期望独立的事件可以分开考虑，