费马小定理

若 $p$ 是质数，则对于任意整数 $a$，有 $$a^{p} \equiv a \pmod {p}$$
推论：$$a^{p-1} \equiv 1 \pmod{p}$$

欧拉定理

若正整数 $a,p$互质，则 $a^{\phi(p)} \equiv 1 \pmod{p}$，其中$\phi(p)$为$p$的欧拉函数。
推论：
当$a,p$互质时，有：
$$a^{p} \equiv a^{b \pmod {\phi(p)}} \pmod{p}$$
当$a,n$不互质时，有：
$$a^{b} \equiv a^{b \pmod {\phi(p)}+\phi(p)} \pmod{p}$$

多个数的$gcd$

设$a_1,a_2,a_3,....a_n$为一个正整数序列，则：
$$gcd(a_1,a_2,a_3,....a_n) = gcd(a_1,a_2-a_1,a_3-a_2,....a_n-a_{n-1})$$
即原数组的$gcd$等于差分数组的$gcd$。

中国剩余定理

设$m_{1},m_{2},m_{3},....,m_{n}$两两互质，$m=\prod_{i=1}^{n}m_{i}$，$M_{i}=m/m_{i}$，$t_{i}$是$M_{i}$模$m_{i}$的逆元，即$M_{i}*t_{i} \equiv 1 \pmod {m_{i}}$，则如下同余方程：
$$\begin{cases} x \equiv a_{1} \pmod{m_{1}}\\ x \equiv a_{2} \pmod{m_{2}}\\ ....\\ x \equiv a_{n} \pmod{m_{n}}\\ \end{cases} $$
有整数解，解为$\sum_{i=1}^{n}a_{i}M_{i}t_{i}$。
该同余方程的通解为: $x+k*m$。

拓展欧几里得算法

对于任意整数$a,b$，存在一对整数$x,y$，满足$x*a+y*b=gcd(a,b)$。若$gcd(a,b)=1$，则$x$为$a$模$b$的乘法逆元，即$a*x \equiv 1 \pmod{b}$。

Lucas定理

若$p$为质数，则有：$$C_{b}^{a} \equiv C_{b \pmod{p}}^{a \pmod{p}} *C_{b/p}^{a/p}\pmod {p}$$
Lucas定理求组合数的代码模板如下:

int C(int a,int b){ //直接求C(a,b)
    int up=1,down=1;
    for(int i=b;i>b-a;i--)up=up*i%p;
    for(int i=1;i<=a;i++)down=down*i%p;
    return up*qmi(down,p-2)%p; //由于p是质数，可以用费马小定理求逆元
}

int Lucas(int a,int b){ //Lucas定理求组合数
    if(a<p && b<p)return C(a,b);
    return C(a%p,b%p)*Lucas(a/p,b/p)%p;
}

卡特兰数

由$n$个0和$n$个1构成的序列，满足对于序列的任意前缀，前缀中0的数量大于等于1的数量，求这样的序列有多少个？
答案：
$$C_{2*n}^{n}-C_{2*n}^{n-1} $$
推导：
考虑一个n*n的棋盘，我们从最左下角出发，走到右上角，对于路径上经过的任意坐标点$(x,y)$，必须满足$x>=y$，求这样的路径有几条。可以发现，前一个问题中的$01$序列恰好可以对应到第二个问题里的，每一步是向右走还是向上走，并且最终恰好向上走$n$步，向右走$n$步，而坐标点的$x$恰好等于当前已经向右走的步数，坐标点的$y$恰好等于向上走的步数，而要求$x>=y$可以对应成任意前缀中0的数量大于等于1的数量。
因此，两个问题完全等价，我们可以按照如图方式解决第二个问题:

我们首先不受限制地走到终点，共有$C_{2*n}^{n}$种走法，再减去不合法的方案：
任意不合法的方案都可以对应成一条从$(0,0)$走到点$(n-1,n+1)$的路径。
因此不合法的方案数量为：$$C_{2*n}^{n-1}$$
最终答案为:
$$C_{2*n}^{n}-C_{2*n}^{n-1}$$

莫比乌斯函数

莫比乌斯函数的定义如下:
对于任意正整数$x=p_{1}^{a_{1}}p_{2}^{a_{2}}....p_{k}^{a_{k}}$，
$$\mu(x)= \begin{cases} 0，存在a_{i}>1\\ 1，k为偶数\\ -1，k为奇数\\ \end{cases} $$
可用于解决容斥原理问题。