数学知识（一）
一.试除法
- 试除法：对一个数x试除，因为约数成对存在，所以从[2,sqrt(x)]试除
- 注意特判完全平方数x：(i==x/i)?相同是一个约数:不同是一对约数
1.试除法判质数（一个操作数）：AcWing866.试除法判定质数
2.试除法求约数（一个操作数）：AcWing869.试除法求约数
2.试除法求最大公约数+二分（一对操作数）：AcWing 4199. 公约数
二.分解质因数
- 根据算术基本定理，对一个数进行质因数分解
- 注意特判：最后可能有一个大于sqrt(x)的质因数（最多有一个，反证法证明）
1.质因数求约数个数（一个操作数）：AcWing 870. 约数个数
2.质因数求所有约数之和（一个操作数）：AcWing 871. 约数之和
3.求最小整数与自己相乘成为一个完全平方数：AcWing3491.完全平方数 （分解质因数，答案ans==p1×p2....×pi,其中pi为奇数个的质因数）
4.线性筛分解质因数（一组操作数）：AcWing 197. 阶乘分解 （分解质因数：枚举每个质数来分解一组数的质因数）
三.线性筛
- 欧拉筛：根据每一个合数只被自己最小的质因数筛掉一次的线性筛法
1.线性筛质数（一组操作数）：AcWing 868. 筛质数
四.最大公约数
- 欧几里得算法求最大公约数
1.求最大公约数（一对操作数）：AcWing 872. 最大公约数
2.差分+求最大公约数（一组操作数）：AcWing 1246. 等差数列（注意特判等差为0的情况）
3.差比+求最大公约数（一组操作数）：AcWing 1223. 最大比例
（注意最简分数的分子分母必须互质，不然可以约分）
五.欧拉函数
- 欧拉函数：f(n)==1~n中与n互质的个数
- 根据欧拉函数公式，需要用质因数求解：f(n)=n×(p1-1)/p1×(p2-1)/p2…
1.分解质因数求欧拉函数（一个操作数）：AcWing 873. 欧拉函数
2.线性筛求欧拉函数（一组操作数）：AcWing 874. 筛法求欧拉函数
3.快速幂+分解质因数求欧拉函数：AcWing 4968. 互质数的个数（因为a与a^n质因数种类相同，所以欧拉函数f(a^b)=a^(b-1)*f(a)）
六.快速幂
- 根据二进制快速计算次方
1.快速幂（一对操作数）：AcWing 875. 快速幂
2.快速幂求逆元（一对操作数）：AcWing 876. 快速幂求逆元（求逆元==a,p互质+模数p为质数+费马小定理+快速幂）
3.字符串快速幂（一对操作数）：
4.容斥原理+快速幂：AcWing1290.越狱（所以情况减去不越狱的情况==越狱的情况）
七.扩展欧几里得算法
- 扩展欧几里得算法：利用裴蜀定理及其推论求乘法逆元，解线性同余方程，解不定方程
