数论总结(目录)
注:题目典型或解题算法的就以题目作为标题,如质数;算法典型或用处广的就以算法作为标题,如快速幂
参考
质数
定义
对于某个数n(n>=2),在1~n中只有1和n两个约数则为质数
经典算法与题型
约数
定义
某数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必败