整理一些数学基础知识。
算数基本定理
任意一个大于1的正整数都能被唯一分解成有限个质数的乘积，可写作：
其中 $c_i$ 都是正整数，$p_i$ 均为质数，且满足 $p_1<p_2<…<p_m$。
显然的推广：如果两个数没有相同的质因数，则这两个数互质。
裴蜀定理：对于方程 $ax+by=c \ \ \ x,y\in \mathbb{Z}^+$，当且仅当 $gcd(a,b)|c$ 时，有整数解。
gcd/lcm转换：$gcd(a,b)lcm(a,b)=ab$
费马小定理：
若 $gcd(a,m)=1 $，则 $a^{m-1} \equiv 1(mod \ m)$
推广：若 $gcd(a,m)=1$，则 $a^m \equiv m(mod \ m)$
线性同余转换：
欧几里得：$gcd(a,b)=gcd(b,a \ mod \ b) \ \ gcd(a,0)=a \ \ (b\not=0)$
欧拉定理：若 $gcd(a,m)=1$，则 $a^{\phi(m)}\equiv 1(mod \ m)$
拓展欧拉定理：$a^b\equiv a^{b \ mod \ \phi(m)+\phi(m)}(mod \ m)$
Stein算法：
- 均为偶数 $gcd( x,y ) =2gcd( x/2,y/2 )$
- 均为奇数 $gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )$
- $x$ 奇 $y$ 偶 $gcd( x,y ) = gcd( x,y/2 )$
- $x$ 偶$ y$ 奇 $gcd( x,y ) = gcd( x/2,y )$ 或 $gcd( x,y )=gcd( y,x/2 )$
组合排列数：
组合恒等式：
恒等式编号按顺序从 $1$ 开始依次递增。
$\left( \begin{array}{c}n\\k\\\end{array}\right)=\left( \begin{array}{c}n\\{n-k}\\\end{array}\right)$ 组合意义：选出一部分再反选。
$\left( \begin{array}{c}n\\k\\\end{array}\right)=\left( \begin{array}{c}n-1\\k\\\end{array}\right)+\left( \begin{array}{c}n-1\\k-1\\\end{array}\right)$ 组合意义：枚举第一个选或不选。
$\left( \begin{array}{c}n\\k\\\end{array}\right)\left( \begin{array}{c}k\\t\\\end{array}\right)=\left( \begin{array}{c}n\\t\\\end{array}\right)\left( \begin{array}{c}n-t\\k-t\\\end{array}\right)$ 组合意义：把 $n$ 个数中选 $k$ 个再选 $t$ 个转化为 $n$ 中选 $t$ 个再选出 $k-t$ 个。
$\left( \begin{array}{c}n\\k\\\end{array}\right)=\sum_{i=k}^n\left( \begin{array}{c}i-1\\k-1\\\end{array}\right)$ 组合意义：考虑最后一个数选在哪里，如果选在 $i$ 则前 $i-1$ 个中要选出 $k-1$ 个。
$\left( \begin{array}{c}n+m\\k\\\end{array}\right)=\sum_{i=0}^k\left( \begin{array}{c}n\\i\\\end{array}\right)\left( \begin{array}{c}m\\k-i\\\end{array}\right)$ 组合意义：$n+m$ 里面选 $k$ 个，枚举前 $n$ 个里面选多少个。
当 $n-m=k$ 时结合恒等式 $1$ 有 $\sum_{i-1}^n\left( \begin{array}{c}n\\i\\\end{array}\right)^2=\left( \begin{array}{c}2n\\n\\\end{array}\right)$。
$\left( \begin{array}{c}n\\a+b+1\\\end{array}\right)=\sum_{i=a+1}^{n-b}\left( \begin{array}{c}i-1\\a\\\end{array}\right)\left( \begin{array}{c}n-1\\b\\\end{array}\right)$ 组合意义：考虑那个 $1$ 选在 $i$，一边选 $a$ 个一边选 $b$ 个。
若 $b=0$ 则该式退化为恒等式 $4$。
$(a+b)^n=\sum_{i=0}^n\left( \begin{array}{c}n\\i\\\end{array}\right)a^ib^{n-i}$ 组合意义：真他妈难证，背过算了。
当 $a=b=1$ 时，有 $\sum_{i=0}^n\left( \begin{array}{c}n\\i\\\end{array}\right)=2^n$。
当 $a=-1,b=1$ 时，有$\sum\left( \begin{array}{c}n\\2k\\\end{array}\right)-\sum\left( \begin{array}{c}n\\2k+1\\\end{array}\right)=0(n\ge1)$
递推阶乘逆元：$\frac{1}{(n-1)!}=\frac{n}{n!}$
递推求组合数的方法：
- 杨辉三角递推，见组合恒等式 $2$。
- 预处理阶乘，递推处理阶乘逆元，对小质数很可能失效（可用卢卡斯补救）。
Lucas定理：$\left( \begin{array}{c}n\\m\\\end{array}\right)\equiv\left( \begin{array}{c}\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\\\end{array}\right)\left( \begin{array}{c}n \ mod \ p\\m \ mod \ p\\\end{array}\right) \ (mod \ p)$
容斥原理：规律为奇加偶减。
错置排序：$D_n=n!(\sum_{i=0}^n\frac{(-1)^i}{i!})$
组合排列问题常见模型：
捆绑法：多个对象排列在一起的问题把这些对象合并为一个整体，先考虑整体的组合再考虑整体内部的组合。
插空法：多个对象要分开时，把其他对象排好再在空隙中插入。
插板法：
对于求 $x_1+x_2+…+x_n=m$ 的正整数解，考虑是在 $m$ 个球的 $m-1$ 个空隙中插入 $n-1$ 个板子，因此答案是 $C^{n-1}_{m-1}$。
对于求 $x_1+x_2+…+x_n=m$ 的非负整数解，实际上可以直接把 $x_i$ 变为 $x_i+1$，答案为 $C_{m+n-1}^{n-1}$。
组合排列常用结论：
斯特林数
第一类
定义：$s(n,k)$ 表示 $n$ 个元素构成 $k$ 个圆排列的方案数。
递推公式：$s(n,k)=s(n-1,k-1)+(n-1)\times s(n-1,k)$。
第二类
定义：$s(n,k)$ 表示把 $n$ 个不同的元素放入 $k$ 个无差别盒子的方案数。
递推公式：$s(n,k)=s(n-1,k-1)+k\times s_2(n-1,k)$。
圆排列：$n$ 个元素组成一个长度为 $m$ 的圆排列的方案数为 $A_n^m/m$。