一些数学结论

质数相关:

1. 一个合数N，一定存在一个质数<=$\sqrt{N}$并整除N(用于大范围判断质数—求出$\sqrt{N}$的质数表)
2. 一个合数N(<1e9)最多含有10种不同的质数因子(最小的10种质数相乘已超过1e9)，每种质数因子的指数不超过30(2^31>1e9)
3. 求N!阶乘的质数分解形式，则统计1~N中各个质数的指数和，即$\frac{N}{p}+\frac{N}{p^2}+\frac{N}{p^3}+...$(为何不是$2*\frac{N}{p^2}$—其中一个已统计过)
4. gcd(n,x)=gcd(n,n-x)，所以与n不互质的数成对出现—与n互质的数也成对出现(平均值为n/2)，故与n互质的数的和=$n/2*{\phi}{n}$
5. gcd(a,b)=gcd(a,b-a),gcd(a,b,c)=gcd(a,b-a,c-b),当数目更多时同样成立，即多个数的gcd等价于其等差数组的gcd。如用线段树，区间修改数组，区间查询gcd，可用A数组记录数组初始值，用B数组维护差分数组，每次修改就转化成了两次单点修改，询问就转化成了求gcd(A[l],ask(l+1,r))
6. 若$a^{x}=1(mod n)$,若a、n互质,则最小的正整数x为${\phi}(n)$的约数(反证法—若不为约数,则$x=k*{\phi}(n)+r$,则r更小且满足条件)
7. 求a%mod的值，而mod为非质数(如999911658)，可将mod分解成质数积，如999911658=2*3*4679*35617,分别计算a%2,a%3,a%4679,a%35617,这几个数互质,可得出一个线性同余方程组,运用CRT求解得到a%mod的值
8. 原根、离散对数:给定质数p，若有一个数r满足gcd(r,p)=1,且$r^{1}~r^{p-1}$次方刚好遍历了$Z_{p}$(即小于p且与p互质的所有数)，则称r是p的原根(dft/idft中，998244353的对应原根是3，其他模数的原根:https://blog.csdn.net/weixin_45697774/article/details/115732914)，而$$r^{e}=a(mod p)$$，则称e是以p为模，以r为底时，a所对应的离散对数。原根具有循环性，被应用于模意义下的fft。
9. 伪素数:若$a^{n-1}==1(mod n)$，且n是合数，则称n是以a为底的伪素数，实践中可通过取多个底来判断n是否是素数(注意，存在合数，满足其是任意底的伪素数，故没法百分百确定)
10. 若a+b=c,则a与b互质的充要条件是a和c也互质(故a+b=c且a与b互质的对数为phi[c])
11. 计算阶乘相关时,可能出现分子,分母阶乘mod后均为0,实际结果不为0的情况(因为可能其因数相消将mod数p消去),此时要求出各个阶乘提取p后的结果—根据威尔逊定理((p-1)!==-1 mod p)

约数相关:

1. 对任意的x<=i<=k/(k/x),k/i结果均相同
2. 对任意的1<=i<=k,k/i最多有$2*\sqrt{k}$种结果(结合1可快速对k/i区间求和)

排列组合相关:

1. i个数的错排总数:f[i]=(i-1)*(f[i-1]+f[i-2]),f[1]=0,f[0]=1(例题:https://www.acwing.com/problem/content/description/232/)

2. 给定一个子串，求长度为m的母串，满足该子串是该母串的不连续子序列的总数：首先，明确如何在母串中规定出“唯一”子串的位置，假设子串为s，母串为p，s[i]与p[j]匹配，s[i+1]与p[k]匹配，则p[j+1]~p[k-1]中，不允许出现s[i](若出现，则该位置才是s[i]匹配位置)，通过该方法，我们可根据子串的字符在母串中的匹配位置(易知匹配位置不同，则母串必不同，故不会重合)，计算该匹配位置有多少种母串(根据上述限制)，而不同的匹配位置可使用dp[i][j]表示母串的第i个字符匹配子串的第j个字符表示，进而递推(来源:https://blog.nowcoder.net/n/aaf4e85f4c7c4c059de3c9c4f2ff91fc)

3. $$\sum_{k=1}^{n}{(-1)^{k} }C(n,k)=(1-1)^{n}=0$$
4. $$\sum_{k=1}^{n}{(2)^{k} }C(n,k)=(2+1)^{n}=3^{n}$$
5. $$C(n+1,k)=C(n,k-1)+C(n,k)$$

6. 范德蒙德恒等式:$C(m+n,r)=\sum_{k=0}^{r}C(m,k)*C(n,r-k)$,进而$C(2n,n)=\sum_{k=0}^{n}{C(n,k)}^{2}$

7. $C(n+1,r+1)=\sum_{j=r}^{n}C(j,r)$(01串中，枚举最后一个1的出现位置从r+1到n+1)