省选前最后一周了，对照大纲过一遍，每个算法稍微写一点自己的理解与板子记忆技巧。
感觉很多东西还是之前听别人讲的时候学的似懂非懂......导致现在看起来好像啥都会一点实际上好像啥也不会，每次越临近考试就会感觉整个人很虚无啊......反正不是很好受。
数论
- exgcd【7】
用于解决形如 \(ax+by=c\) 的整数域不定方程，有解的条件是 \(\gcd(a,b)|c\)（裴蜀定理 【7】）。
具体地，对于方程 \(ax+by=c\)，辗转相除构造 \(a=b',b=a \bmod b\) 的解 \((x',y')\)，那么 \(x=y'\)，\(y=x'-\lfloor\frac{a}{b}\rfloor y'\)，边界条件 \(b=0\) 时 \(x=1,y=0\)，容易验证其正确性。
得到是一组特解，如果需要求最小最大解 / 正整数解之类的其他要求，直接调整即可。所有解和特解的关系形如 \(x=x_0+kb,y=y_0-ka\)。
void exgcd(ll a,ll b,ll&x,ll&y){
if(!b)return x=1,y=0,void();
exgcd(b,a%b,y,x);
y-=a/b*x;
}
- 费马小定理 【7】
\(a^{p-1}\equiv 1\pmod p\)，\(p\) 是质数，常用于求模质数意义下的逆元。
- 威尔逊定理 【7】
\((p-1)!\equiv -1\pmod p\)，证明考虑两两分组乘起来。
- 欧拉定理和欧拉函数 【7】
欧拉函数 \(\varphi(n)\) 表示 \([1,n]\) 中与 \(n\) 互质的正整数个数，是积性函数，可以线性筛求。
常用结论：\(\sum\limits_{d|n}\varphi(d)=n\)，证明考虑组合意义。
（扩展）欧拉定理：当 \(b\ge \varphi(p)\) 时 \(a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\pmod p\)（欧拉降幂法）
- exCRT 【7？】
exCRT 可以完全替代 CRT。
要求形如 \(x\equiv a_i \pmod {p_i}\) 的方程组。
考虑依次合并各个方程组，那么现在问题变为，已知前 \(i-1\) 个方程组的某个解为 \(x\)，前 \(i-1\) 个 \(p\) 的 LCM 为 \(M\)，那么调整这个 \(x\)，加上 \(M\) 的倍数使得 \(x\) 满足第 \(i\) 个方程组。用形式化的语言描述就是 \(x+Mt\equiv a_i\pmod{p_i}\)，移项得到 \(Mt\equiv a_i-x\pmod{p_i}\)，可以表示为 \(Mt+p_is=a_i-x\) 的二元一次不定方程的形式，用 exgcd 解决。
- 原根和指数 【8】