数论总结（目录）

注：题目典型或解题算法的就以题目作为标题，如质数；算法典型或用处广的就以算法作为标题，如快速幂

参考

• y总数论模版
• 大佬数论总结

质数

定义

对于某个数n(n>=2)，在1～n中只有1和n两个约数则为质数

经典算法与题型

• 判定质数 ——试除法
• 分解质因式 ——试除法
• 筛素数
  1.试除法
  2.埃式筛法
  3.线性筛法

约数

定义

某数n能被d整除，那么定义d是n的一个约数

经典算法与题型

• 求某数所有约数——试除法
• 求约数个数——试除法分解质因式
• 求约数之和——试除法分解质因式
• 最大公约数——欧几里得算法

欧拉函数

定义

n在1～N中与N互质的数的个数为欧拉函数，记作$\phi(N)$
若$N=p_1^{a_1}p_2^{a_2}…p_m^{a_m}$,则$\phi(N)=N\times \frac{p_1-1}{p_1}\cdot \frac{p_2-1}{p_2}…\frac{p_m-1}{p_m}$
欧拉定理：$\alpha^{\phi(n)} \equiv 1\pmod n$

经典算法与题型

• 定义求欧拉函数——试除法分解因式
• 筛法求欧拉函数——筛素数

快速幂

定义

快速计算$(a^b\bmod p)$值的算法叫做快速幂

经典算法与题型

• 计算$(a^b\bmod p)$——快速幂
• 求逆元——快速幂
• 各种求高次幂的问题都可以用快速幂！,例如求膜为质数的逆元

扩展欧几里得算法

定义

利用欧几里得算法同时求出其他信息，例如可求解出线性同余方程$ax+by=gcd(a,b)$中的系数x,y

经典算法与题型

• 求裴蜀定理系数——扩展欧几里得
• 求解线性同余方程——扩展欧几里得
• 中国剩余定理——扩展欧几里得

高斯消元

定义

经典线性代数中，用来解多元线性方程组的方法

经典算法与题型

• 求解线性方程组——高斯消元
• 异或线性方程组——高斯消元

求组合数

定义

从a个物品中拿取b个物品的组合数，即$C_{a}^{b}$

经典算法与题型

• 求组合数1——dp预处理组合数
• 求组合数2——dp预处理阶乘+快速幂求逆元
• 求组合数3——Lucas定理
• 求组合数4——高精度乘法
• 满足条件的01序列数——卡特兰数+组合数求解

容斥原理

定义

计算n个集合并集后的元素个数的原理，即计算$\bigcup_{i=1}^{n}S_i$的原理

经典算法与题型

• 能被整除的数的个数——容斥原理

博弈论

定义

博弈游戏中的规律，此处特指nim游戏规律。nim游戏规律：在公平的有向图游戏中，先手碰到所有初始状态异或和不为0必胜，为0必败

经典算法与题型

• 经典Nim游戏——nim游戏规律
• 台阶Nim游戏——nim游戏规律
• 集合Nim游戏——sg函数+nim游戏
• 拆分Nim游戏——sg函数+nim游戏