基本数学知识：
1.质数：大于1的整数，如果只包含1和本身两个约数，那么称质（素）数
试除法：定义出发的O(n) 加入性质：若d|n 那么一定有 n/d|n 换句话说约数一定成对出现，那么只需枚举 d<=n/d 即
d^2<=n 即可for(int i=2;i<=n/i;i++)推荐写成这样，如果使用sqrt函数反复调用较慢，如果使用i*i<=n可能有溢出风险
时间复杂度O(sqrt(n))

试除法分解质因子：优化方法与试除法判断质数相同，首先知道一个结论n中最多只包含一个>sqrt(n)的质因子,所以只要枚举根号n之内的数即可，同时无论枚举多少数都不用担心枚举到合数。时间复杂度：最好时O(logn)最坏时O(sqrt(n))

素数筛：
1.朴素做法：先将数填入数表，之后枚举每个数，把这些数的倍数删掉，经过这样的操作结束之后剩下的就一定是质数（因为对于i来说经过这样的操作之后一定能保证在2~i-1中没有i的约数） 时间复杂度（n/2+n/3+......+n/n）调和级数的极限是lnn所以朴素筛法的复杂度为O(nlogn)

做优化：并不需要全部枚举，可以只把原来枚举范围中的质数枚举即可，把所有质数的倍数删掉即可。
质数定理：在1~n中有n/lnn个质数，相当于优化之后只需要算n/lnn个数的调和级数
这个筛法也叫作埃氏筛法

2.线性筛法；
核心：n只会被它的最小质因子筛掉
void get_prime(int x){ for(int i=2;i<=x;i++){ if(!st[i])//没有被筛掉 prime[cnt++]=i;//说明i是质数，加入数组当中 for(int j=0;prime[j]<=x/i;j++){//从小到大枚举pj st[prime[j]*i]=true;//只用最小质因子来筛的某个数 if(i%prime[j]==0)break;//由于从小到大枚举pj这样可以保证pj一定是i的最小质因子，并且pj一定也同时是pj*i的最小质因子 当i%pj!=0的时候这时候还没有找到任何一个质因子，由于pj从小到大枚举说明这时，pj一定小于i的所有质因子，pj也一定是pj*i的最小质因子。 证明所有合数都一定会被筛掉：对于一个合数x，假设pj是x的最小质因子，当i枚举到x/pj的时候，（i枚举到x之前一定会枚举到x/pj也一定会在这时把x筛掉） 时间复杂度：每个数都只会被最小质因子筛掉，每个数都只有一个最小质因子，每个数只会被筛一次，所以是线性的。 } } }
2.约数:
1.试除法：同质数，约数也是成对出现的所以有sqrt(n)的优化方法
2.算术基本定理求约数个数：假设N=p1^a1+p2^a2+......+pk^ak 那么 N的约数个数一定=(a1+1)*(a2+1)......*(ak+1)
证明：因为N的任何一个约数d也一定 有 类似上边的形式 (0<=bk<=ak)
由于每个数的因式分解是唯一的，所以a1......ak有多少种选法就说明因式分解有多少种，就说明能确定多少N的约数
3.约数之和：有前面求个数的基础，可以得知有公式;sum=(p1^0+p1^1+......+p1^a1)*(pk^0+pk^1+......+pk^ak)
证明：只需要展开上述公式即可得到约数和的形式
4.求最大公约数：
欧几里得算法（辗转相除法）：
时间复杂度：O(logn)
首先明确数论的一些基本性质：如果d|a,d|b那么一定有d|(a+b)也有d|(ax+by)，根据这个性质就有(a,b)表示ab的最大公约数 (a,b)=(b,a mod b)
证明这个性质是正确的：a mod b == a-[a/b]*b([a/b]是向下取整，并且这一定是一个整数记为c) 故 a mod b == a-c*b
若有(a,b)则有d|a,d|b，由基本性质知d|a-c*b，至此证明左边任何一个公约数都是右边的公约数，同理对于右边来说d|b，d|a-c*b既然有这个式子就一定有d|a-c*b+c*b==d|a，所以证明右边任何一个公约数d都是左边的公约数，综上，两边公约数集合是相同的，所以等式成立，性质存在。

3.求组合数：
1.10w组询问，每组询问数据范围<=2000。 使用递推公式即可 O(n^2)
2.1w组询问，每组询问数据范围<=1e5 预处理阶乘和逆元，用公式求。O(nlogn)
3.20组询问，每组询问数据范围<=1e18，p<=1e5 lucas定理 O(plogplogn)
4.高精度 用高精度乘法处理。