初等数论及组合数学入门复习概览

同步于 博客园 和 洛谷博客。

由于各网站之间 $\LaTeX$ 及 Markdown 渲染方式的差异，故不保证除博客园外的排版完好，对于排版有明显不正确的地方请以博客园为主。

质数

定义：无法被任何除了 $1$ 及其本身的自然数整除的数。

性质：

1. $[1,n]$ 内大约有 $\frac{n}{\ln n}$ 个质数，即每 $\ln n$ 个数就大约有一个质数。

判断质数

1. 试除法：

时间复杂度 $\mathcal{O}(\sqrt{n})$。

bool isPrime(int n){
    if (n<2) return 0;
    int k=sqrt(n);
    F(i,2,k)
        if (!(n%i)) return 0;
    return 1;
}

质数筛

1. 埃氏筛：

对于每个整数，显然其倍数都不是质数。

扫描所有数，每扫到一个没被标记的数，该数即为质数，随后标记该数的倍数为约数。

同时，对于当前的质数 $x$，因为小于 $x^2$ 的 $x$ 的倍数已经被小于 $x$ 的质数扫描过了，因此只需要从 $x^2$ 开始扫描倍数即可。

时间复杂度 $\mathcal{O}(n\log \log n)$。

bool vis[N];
void EratosthenesSeive(int n){
    F(i,2,n){
        if (vis[i]) continue;
        F(j,i,n/i) vis[i*j]=1;
    }
    return ;
}

2. 线性筛（欧拉筛）：

埃氏筛依旧会重复标记某些合数，考虑使合数被唯一标记。

设 $v_i$ 为 $i$ 的最小质因子，从前到后扫描所有数，若 $v_i=0$ 则 $i$ 为质数，使 $v_i=i$ 并将 $i$ 加入到质数集 $\text{Prime}$。

对于每个数，扫描质数集的所有数 $x$，若 $x$ 相比 $v_i$ 不是最小的质因子或 $i\times x$ 超出筛的范围则终止扫描，反之则 $v_{i\times x}=x$。

时间复杂度 $\mathcal{O}(n)$。

vector<int> prime;
int v[N];
void EulerSeive(int n){
    F(i,2,n){
        if (!v[i]) v[i]=i,prime.push_back(i);
        V(x,prime){
            if (x>v[i]||i*x>n) break;
            v[i*x]=x;
        }
    }
    return ;
}

质因数分解

前置知识：

1. 唯一分解定理：任意一个大于 $1$ 的正整数 $n$ 都可被唯一分解为若干个质数的乘积，即 $n=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}$，其中 $c_i$ 为正整数，$p_i$ 为质数且 $p_1 < p_2 < \dots < p_k$。

int p[N],c[N],tot;
void Divide(int n){
    int k=sqrt(n);
    F(i,2,k){
        if(!(n%i)){
            p[++tot]=i,c[tot]=0;
            while(!(n%i)) ++c[tot],n/=i;
        }
    }
    if (n>1) p[++tot]=n,c[tot]=1;
    return ;
}

约数

定义：若 $n\bmod d=0$，则称 $d$ 为 $n$ 的约数，记作 $d\mid n$，读作 $d$ 整除 $n$。

求单个值的正约数集合

1. 试除法：

因为若 $d$ 为 $n$ 的约数，则 $\frac{n}{d}$ 也为 $n$ 的约数，所以除完全平方数的 $\sqrt n$ 之外，约数总是成对出现的。

故从 $1\sim \sqrt n$ 判断 $i$ 是否整除 $n$ 即可，若整除且 $i\neq \frac{n}{i}$ 则 $\frac{n}{i}$ 也为约数。

推论：一个整数 $n$ 至多有 $2\sqrt n$ 个约数。

时间复杂度 $\mathcal{O}(\sqrt n)$。

vector<int> fac;
void FactorDivision(int n){
    int k=sqrt(n);
    F(i,1,k){
        if (!(n%i)){
            fac.push_back(i);
            if (i!=n/i) fac.push_back(n/i);
        }
    }
    return ;
}

求区间内的正约数集合

1. 暴力+试除法：

时间复杂度 $\mathcal{O}(n\sqrt n)$，代码见求单个值的正约数集合。

2. 倍数法：

反过来考虑，运用埃氏筛的倍数标记思想，对于每个数 $d$，$d$ 肯定为其的倍数的约数，故对于每个数，将这个数加入到这个数的倍数的正约数集合里。

时间复杂度 $\mathcal{O}(n\log n)$。

vector<int> fac[N];
void FactorDivision(int n){
    F(i,1,n)
        F(j,1,n/i)
            fac[i*j].push_back(i);
    return ;
}

数论分块

例题：给定正整数 $n$，求 $\sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor$，其中 $1\leq n\leq 10^9$。

显然 $\frac{n}{i}$ 在连续的区间内值相等，故可以分成若干块再进行计算。

对于每个块，设 $l$ 为该块的左边界，那么这个块的值为 $k=\lfloor \frac{n}{l} \rfloor$，那么右边界 $r$ 即为最大的 $i$，且满足 $i\leq \frac{n}{k}$，故 $r=\lfloor \frac{n}{k} \rfloor$，代入 $k$ 得 $r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$。

时间复杂度 $\mathcal{O}(\sqrt n)$。

int mathBlock(int n){
    int l=1,r,ans=0;
    while(l<=n){
        r=n/(n/l);
        ans+=(n/l)*(r-l+1);
        l=r+1;
    }
    return ans;
}

题目：

• [AHOI2005]约数研究
• 约数和

最大公约数 最小公倍数

前置知识：

1. 公约数：若 $x\mid a$ 且 $x\mid b$，则称 $x$ 为 $a$ 和 $b$ 的公约数。

2. 公倍数：若 $a\mid x$ 且 $b\mid x$，则称 $x$ 为 $a$ 和 $b$ 的公倍数。

显然最大公约数就是公约数中最大的数字，最小公倍数就是公倍数中最小的数字。

求最大公约数

1. 欧几里得算法：

$\gcd(a,b)=\gcd(b,a\bmod b)$

设 $a > b$ 且 $a=bk+c$，则有 $c=a\bmod b$。
设 $d\mid a,d\mid b$，则有：

$$\begin{aligned} c=a-bk\\ \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k \end{aligned}$$

由对 $d$ 的定义可知 $d\mid c$，故 $\gcd(a,b)=\gcd(b,a\bmod b)$，得证。

时间复杂度 $\mathcal{O}(\log n)$。

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

2. 更相减损术：

$\gcd(a,b)=\gcd(a-b,b)$

当 $a=b$ 时，显然 $\gcd(a,b)=a=b$。
设 $a\geq b$，那么 $\forall d\mid a,d\mid b$ 有 $d\mid a-b$。
故 $a$ 和 $b$ 的所有公约数都为 $a-b$ 和 $b$ 的公约数，$\gcd(a,b)=\gcd(a-b,b)$，得证。

时间复杂度 $\mathcal{O}(\max(a,b))$。

int gcd(int a,int b){
    while(a!=b){
        if (a>b) a-=b;
        else b-=a;
    }
    return a;
}

3. 更相减损术优化：

若 $2\mid a$ 且 $2\mid b$，则 $\gcd(a,b)=2\gcd(\frac{a}{2},\frac{b}{2})$。

反之，则若 $2\mid a$ 且 $2\nmid b$，则 $\gcd(a,b)=\gcd(\frac{a}{2},b)$。

当 $2\nmid a,2\mid b$ 时同理。

时间复杂度 $\mathcal{O}(\log n)$。

int gcd(int a,int b){
    int aa=0,bb=0;
    while(!(a&1)) a>>=1,++aa;
    while(!(b&1)) b>>=1,++bb;
    while(1){
        while(!(a&1)) a>>=1;
        while(!(b&1)) b>>=1;
        if (a==b) break;
        if (a<b) swap(a,b);
        a-=b;
    }
    return a<<min(aa,bb);
}

求最小公倍数

$\gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b$

由唯一分解定理，可使 $a=p_1^{c_{a_1}}p_2^{c_{a_2}}\dots p_k^{c_{a_k}},b=p_1^{c_{b_1}}p_2^{c_{b_2}}\dots p_k^{c_{b_k}}$。
则最大公约数为 $p_1^{\min(c_{a_1},c_{b_1})}p_2^{\min(c_{a_2},c_{b_2})}\dots p_k^{\min(c_{a_k},c_{b_k})}$，最小公倍数为 $p_1^{\max(c_{a_1},c_{b_1})}p_2^{\max(c_{a_2},c_{b_2})}\dots p_k^{\max(c_{a_k},c_{b_k})}$。
由于 $\min(c_a,c_b)+\max(c_a,c_b)=c_a+c_b$，所以 $\gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b$，得证。

时间复杂度为求最大公约数的时间复杂度。

int lcm(int a,int b){
    // 先除后乘可防止爆 int。
    return a/gcd(a,b)*b;
}

欧拉函数

前置知识：

1. 互质：$\forall x,y\in \mathbb{N}$，若 $\gcd(x,y)=1$，则称 $x$ 和 $y$ 互质，记作 $x\perp y$。

2. 积性函数：若 $x,y$ 互质且 $f(x)\times f(y)=f(xy)$，则称函数 $f$ 为积性函数。

3. 完全积性函数：若 $\forall x,y\in \mathbb{R}$，$f(x)\times f(y)=f(xy)$，则称 $f$ 为完全积性函数。

定义：$\forall n>1$，$\sum_{i=1}^{n}[i\perp n]$，记作 $\varphi(n)$，特别地，$\varphi(1)=1$。

性质：

1. 若 $n$ 为质数，则 $\varphi(n)=n-1$。

2. $\forall n>1$，$\sum_{i=1}^{n}[i\perp n]\times i=\frac{n}{2}\times \varphi(n)$。

$\because \gcd(n,x)=\gcd(n,n-x)$

$\therefore$ 若 $x$ 不与 $n$ 互质，则 $n-x$ 也不与 $n$ 互质，且 $x$ 和 $n-x$ 总成对出现，其平均值为 $\frac{n}{2}$。

$\therefore$ 与 $n$ 互质的数的平均值为 $\frac{n}{2}$，而与 $n$ 互质的数有 $\varphi(n)$ 个，得证。

3. $\varphi$ 为积性函数，即若 $x,y$ 互质，则 $\varphi(xy)=\varphi(x)\times \varphi(y)$。

4. 若 $n=p^k$，且 $p$ 为质数，则 $\varphi(n)=(p-1)\times p^{k-1}$。

根据唯一分解定理，可知 $n$ 与 $p$ 的倍数都不互质，与其它数均互质。

$p$ 的倍数有 $p^{k-1}$ 个（含 $n$ 本身），故 $\varphi(n)=p^k-p^{k-1}=(p-1)\times p^{k-1}$，得证。

5. 若 $p$ 为质数，且 $p$ 为 $n$ 的约数，则 $\varphi(np)=\varphi(n)\times p$。

因为 $p$ 为质数，所以 $np$ 和 $n$ 的质因子相同，仅 $p$ 的指数不同，故（计算公式见求单个值的欧拉函数）：

$$\frac{\varphi(np)}{\varphi{(n)}}=\frac{np\times\prod_{i=1}^{k}(1-\frac{1}{p_i})}{n\times \prod_{i=1}^{k}(1-\frac{1}{p_i})}=\frac{np}{n}=p$$

所以 $\varphi(np)=\varphi(n)\times p$，得证。

6. 若 $p$ 为质数且 $p$ 不为 $n$ 的约数，则 $\varphi(np)=\varphi(n)\times (p-1)$。

因为 $p$ 不为 $n$ 的约数，所以 $p\perp n$。
故 $\varphi(np)=\varphi(n)\times \varphi(p)=\varphi(n)\times (p-1)$，得证。

7. $\sum_{d\mid n}\varphi(d)=n$

设 $f(x)=\sum_{d\mid n}\varphi(d)$，因为 $\varphi$ 为积性函数，所以若 $a,b$ 互质，则 $f(ab)=\sum_{d\mid ab}\varphi(d)=(\sum_{d\mid a}\varphi(d))\times (\sum_{d\mid b}\varphi(d))$，所以 $f$ 为积性函数。
对于一个质因子 $p^k$，$f(p^k)=\sum_{d\mid p^k}\varphi(d)=\varphi(1)+\varphi(p)+\dots+\varphi(p^k)$，结果为等比数列求和加 $1$，结果为 $p^k$。
故 $f(n)=\prod_{i=1}^{k}f(p_i^{c_i})=\prod_{i=1}^{k}p_i^{c_i}=n$，得证。

求单个值的欧拉函数

通过唯一分解定理，使 $n=p_1^{c_1}\times p_2^{c_2}\times \dots \times p_k^{c_k}$，则：

$$\varphi(n)=n\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \dots \frac{p_k-1}{p_k}=n\times \prod_{i=1}^{k}(1-\frac{1}{p_i})$$

对于 $n$ 的所有质因子 $p_i$，在 $1\sim n$ 范围内 $p_i$ 的倍数有 $\frac{n}{p_i}$ 个。
那么对于 $n$ 的两个质因子 $p,q$，根据容斥，$1\sim n$ 范围内含质因子 $p$ 或 $q$ 的数的个数为 $\frac{n}{p}+\frac{n}{q}-\frac{n}{pq}$。
不含质因子 $p$ 或 $q$ 的数的个数为 $n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}=n\times (1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq})=n(1-\frac{1}{p})(1-\frac{1}{q})$，将公式扩展到所有质因子 $p_i$ 即可得证。

故在分解质因数时即可求出 $\varphi$，时间复杂度 $\mathcal O(\sqrt n)$。

int Phi(int n){
    int ans=n,k=sqrt(n);
    F(i,2,k){
        if (!(n%i)){
            ans=ans/i*(i-1);
            while (!(n%i)) n/=i;
        }
    }
    if (n>1) ans=ans/n*(n-1);
    return ans;
}

求区间内的欧拉函数

1. 暴力：

代码见求单个数的欧拉函数，时间复杂度 $\mathcal O(n\sqrt n)$。

2. 埃氏筛：

时间复杂度 $\mathcal O(n\log n)$。

int phi[N];
void CalculatePhi(int n){
    F(i,1,n) phi[i]=i;
    F(i,2,n){
        if (phi[i]==i)
            for (int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i+1);
    }
    return ;
}

3. 线性筛：

时间复杂度 $\mathcal O(n)$。

int phi[N],v[N];
vector<int> prime;
void CalculatePhi(int n){
    phi[1]=1;
    F(i,2,n){
        if (!v[i])
            v[i]=i,phi[i]=i-1,prime.push_back(i);
        V(x,prime){
            if (x>v[i]||i*x>n) break;
            v[i*x]=x;
            phi[i*x]=phi[i]*(i%x?x-1:x);
        }
    }
    return ;
}

题目：

• GCD SUM
• [SDOI2008] 仪仗队

莫比乌斯函数

定义：若根据唯一分解定理使正整数 $n=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}$，则有：

$$\mu(n)= \begin{cases} 0,\exists i \in [1,k],c_i > 1\\ 1,m\equiv 0\pmod 2,\forall i \in [1,m],c_i=1\\ -1,m\equiv 1\pmod 2,\forall i \in [1,m],c_i=1 \end{cases}$$

特别地，$\mu(1)=1$。

求单个值的莫比乌斯函数

1. 质因数分解：

时间复杂度 $\mathcal{O}(\sqrt n)$。

int Mobius(int n){
    if (n==1) return 1;
    int k=sqrt(n),cnt=0;
    F(i,2,k){
        if (!(n%i)){
            int ci=0;
            while(!(n/i)) n/=i,++ci;
            if (ci>1) return 0;
            ++cnt;
        }
    }
    if (n>1) ++cnt;
    return cnt&1?-1:1;
}

求区间内的莫比乌斯函数

1. 埃氏筛：

先初始化 $\forall i\in [1,n],\mu(i)=1$，显然对于质数 $n$ 有 $\mu(n)=-1$，对于 $n$ 的倍数，若 $n^2\mid kn$，则说明出现了 $c_i > 1$ 的情况，$\mu(kn)=0$，反之则 $\mu(kn)=-\mu(kn)$。

时间复杂度 $\mathcal{O}(n\log \log n)$。

int mu[N];
bool vis[N];
void Mobius(int n){
    fill(mu+1,mu+1+n,1);
    F(i,2,n){
        if (vis[i]) continue;
        mu[i]=-1;
        for (int j=(i<<1);j<=n;j+=i){
            v[j]=1;
            if (!((j/i)%i)) mu[i]=0;
            else mu[i]*=-1;
        }
    }
    return ;
}

2. 线性筛：

对于质数 $n$ 及每一个被遍历到的合数 $n\times v_i$，若其出现 $c_i > 1$，则停止遍历，否则 $\mu(n\times v_i)=-\mu(n)$。

时间复杂度 $\mathcal{O}(n)$。

vector<int> prime;
int mu[N];
bool vis[N];
void Mobius(int n){
    mu[1]=1;
    F(i,2,n){
        if (!vis[i]) vis[i]=1,mu[i]=-1,prime.push_back(i);
        V(x,prime){
            if (i*x>n) break;
            vis[i*x]=1;
            if (!(i%x)) break;
            mu[i*x]=-mu[i];
        }
    }
    return ;
}

同余

前置知识：

1. 取模的定义式：

$$a\bmod p= \begin{cases} a-\lfloor \frac{a}{p} \rfloor \times p,a\geq 0\\ -(-a\bmod p),a<0 \end{cases}$$

定义：若 $x\bmod p=y\bmod p$，则称 $x,y$ 模 $p$ 同余，记作 $x\equiv y\pmod p$。

性质：

1. 自反性：$x\equiv x\pmod p$。

2. 对称性：若 $x\equiv y\pmod p$，则 $y\equiv x\pmod p$。

3. 传递性：若 $x\equiv y\pmod p$ 且 $y\equiv z\pmod p$，则 $x\equiv z\pmod p$。

4. 同余式相加性：若 $x\equiv y\pmod p$ 且 $a\equiv b\pmod p$，则 $(x\pm a)\equiv (y\pm b)\pmod p$。

5. 同余式相乘性：若 $x\equiv y\pmod p$ 且 $a\equiv b\pmod p$，则 $ax\equiv by\pmod p$。

乘法逆元

前置知识：

1. 费马小定理：若 $p$ 为质数且 $a\perp p$，则 $a^p\equiv a\pmod p$。

定义：若 $a\perp p$ 且 $x$ 为 $ax\equiv 1\pmod p$ 的解，则称 $x$ 为 $a$ 模 $p$ 的乘法逆元，记作 $a^{-1}\pmod p$。

求单个值的乘法逆元

若 $a\not \perp p$，则不存在 $a$ 模 $p$ 的乘法逆元。

1. 快速幂：若 $p$ 为质数，且 $a\perp p$，根据费马小定理，可知 $a$ 模 $p$ 的乘法逆元为 $a^{p-2}\bmod p$。

由费马小定理可知 $a^{p-1}\equiv 1\pmod p$。
而我们要求 $ax\equiv 1\pmod p$ 的解，由传递性可得：

$$\begin{aligned} ax\equiv a^{p-1}\pmod p\\ x\equiv a^{p-2}\pmod p \end{aligned}$$

得证。

2. 扩展欧几里得算法：将方程改写为 $ax+py=1$，使用扩展欧几里得算法求出 $x$ 即可。

题目：

• [NOIP2012 提高组] 同余方程

求区间内的乘法逆元

1. 暴力+快速幂：

仅适用于 $p$ 为质数且 $a\perp p$ 的情况，时间复杂度 $\mathcal{O}(n\log p)$。

2. 暴力+扩展欧几里得算法：

代码见扩展欧几里得算法，时间复杂度 $\mathcal{O}(n\log p)$。

3. 线性递推：

$inv_i=-\lfloor \frac{p}{i} \rfloor \times inv_{p\bmod i}\bmod p$，特别地，$inv_1=1$。

设 $p=k\times i+r$，其中 $i$ 为当前的数，$k$ 为 $\lfloor \frac{p}{i} \rfloor$，$r$ 为 $p\bmod i$。

$$\begin{aligned} p \equiv 0 \pmod p\\ k\times i+r \equiv 0 \pmod p \end{aligned}$$

两边同乘 $i^{-1}r^{-1}$ 得：

$$\begin{aligned} k\times r^{-1}+i^{-1} \equiv 0 \pmod p\\ i^{-1} \equiv -k\times r^{-1}\pmod p\\ i^{-1} \equiv -\lfloor \frac{p}{i} \rfloor \times {(p\bmod i)}^{-1} \pmod p \end{aligned}$$

故递推即可，得证。

时间复杂度 $\mathcal{O}(n)$。

inv[1]=1;
F(i,2,n) inv[i]=(p-p/i)*inv[p%i]%p;

题目：

• 【模板】乘法逆元

求区间内阶乘的乘法逆元

1. 线性递推：

$facinv_i=facinv_{i+1}\times (i+1)$，特别地，$facinv_n=inv_{n!\bmod p}$。

$\because facinv_{i+1}=\frac{1}{(i+1)!}$
$\therefore facinv_{i+1}\times (i+1)=\frac{1}{i!}=facinv_i$
得证。

时间复杂度 $\mathcal{O}(n)$。

欧拉定理

前置知识：

1. 同余类：$\forall a\in[0,m-1]$，集合 $\{a+km\}(k\in \mathbb{Z})$ 的所有数模 $m$ 同余，余数均为 $a$，则称该集合为一个模 $m$ 的同余类，记为 $\overline{a}$。

2. 完全剩余系：$m$ 个模 $m$ 的同余类 $\overline{i} (i\in[0,m-1])$ 所构成的集合称为完全剩余系。

3. 简化剩余系：$\varphi(m)$ 个与 $m$ 互质的数的同余类所构成的集合称为简化剩余系。

4. 费马小定理：见乘法逆元。

定义：若 $a\perp p$，则 $a^{\varphi(p)}\equiv 1\pmod p$。

扩展欧拉定理

$$a^b\equiv \begin{cases} a^{b\bmod \varphi(p)},a\perp p\\ a^b,a\not \perp p,b<\varphi(p)\\ a^{b\bmod \varphi(p)+\varphi(p)},a\not \perp p,b\geq \varphi(p) \end{cases} \pmod p$$

题目：

• 【模板】扩展欧拉定理

• [六省联考 2017] 相逢是问候

扩展欧几里得算法

前置知识：

1. 欧几里得算法：见求最大公约数。

2. 裴蜀定理（Bézout 定理）：$\forall a,b\in \mathbb{Z},\exists x,y\in \mathbb{Z},ax+by=\gcd(a,b)$。

在欧几里得算法的最后一步，即 $b=0$ 时，显然存在 $x=1,y=0$ 使 $a\times 1+0\times 0=\gcd(a,0)$。
考虑当 $b>0$ 时，$\gcd(a,b)=\gcd(b,a\bmod b)$，设存在一对整数 $x,y$ 使得 $\gcd(b,a\bmod b)=bx+(a\bmod b)y$。
由取模的定义式，可转化 $bx+(a\bmod b)y=bx+(a-b\lfloor \frac{a}{b} \rfloor)y=ay+b(x-\lfloor \frac{a}{b} \rfloor y)$。
故当 $x^{\prime}=y,y^{\prime}=x-\lfloor \frac{a}{b} \rfloor y$ 时，有 $ax^{\prime}+by^{\prime}=\gcd(a,b)$，对递归过程使用数学归纳法即可得证。

对于求 $ax+by=\gcd(a,b)$ 中 $x,y$ 的值，由裴蜀定理的证明中可知仅需要在欧几里得算法中保存 $x,y$ 即可。

int exgcd(int a,int b,int &x,int &y){
    if (!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}

题目：

• 【模板】二元一次不定方程 (exgcd)

中国剩余定理

前置知识：

1. 乘法逆元：见乘法逆元。

若 $p_1,p_2,\dots,p_n$ 两两互质，求解方程组：

$$\begin{cases} x\equiv a_1\pmod {p_1}\\ x\equiv a_2\pmod {p_2}\\ \vdots \\ x\equiv a_n\pmod {p_n} \end{cases}$$

设 $m=\prod_{i=1}^{n}{p_i}$，$M_i=\frac{m}{p_i}$，$t_i$ 为 $M_i$ 模 $p_i$ 的乘法逆元，则 $x=\sum_{i=1}^{n}{a_iM_it_i}\bmod m$。

$\because M_i$ 为除 $p_i$ 外所有模数的倍数且 $p_1,p_2,\dots,p_n$ 两两互质。
$\therefore \forall k\neq i,a_kM_kt_k\equiv 0\pmod {p_k}$
$\because t_i\equiv(M_i)^{-1}\pmod {p_i}$
$\therefore a_iM_it_i\equiv a_i\pmod {p_i}$
由同余式相加性且 $m=\prod_{i=1}^{n}{p_i}$ 可知 $x$ 在展开之后即为 $\sum_{i=1}^{n}{a_iM_it_i}\bmod m$，得证。

时间复杂度 $\mathcal{O}(n\log p)$。

int CRT(int n){
    F(i,1,n){
        exgcd(M/p[i],p[i],x,y);
        x=(x%p[i]+p[i])%p[i];
        ans+=x*a[i]*(M/p[i]),ans%=M;
    }
    return ans;
}

题目：

• 【模板】中国剩余定理（CRT）/ 曹冲养猪

扩展中国剩余定理

前置知识：

1. 扩展欧几里得算法：见扩展欧几里得算法。

若 $p_1,p_2,\dots,p_n$ 不保证两两互质，则上述结论不成立，需要另外一种解法。

考虑 $n=2$ 的情况，可转化为不定方程 $x=kp_1+a_1=bp_2+a_2,k,b\in \mathbb{Z}$，则有 $kp_1-bp_2=a_2-a_1$。

若 $a_2-a_1 \nmid \gcd(p_1,p_2)$，则无解，反之可用扩展欧几里得算法求出一组解 $(k,b)$。

则 $x\equiv kp_1+a_1\pmod {\operatorname{lcm} (p_1,p_2)}$。

扩展到 $n\neq 2$ 的情况，仅需要依次求解即可。

时间复杂度 $\mathcal{O}(n\log n)$。

int exCRT(int n){
    int ret=a[1],cur=p[1],x,y;
    F(i,2,n){
        int gcd=exgcd(cur,p[i],x,y),c=((a[i]-ret)%p[i]+p[i])%p[i];
        if (c%gcd) return -1;
        x=quick_mul(x,c/gcd,p[i]/gcd);
        ret+=x*cur;
        cur=cur/gcd*p[i];
        ret=(ret%cur+cur)%cur;
    }
    return (ret%cur+cur)%cur;
}

题目：

• 【模板】扩展中国剩余定理（EXCRT）

组合

加法原理 乘法原理

加法原理（分类）：一个问题有 $n$ 类方法，每个类别有 $a_i$ 个不同的方法，那么解决此问题有 $a_1+a_2+\dots+a_n$ 个方法。

乘法原理（分布）：一个问题有 $n$ 个方法，每个方法有 $a_i$ 个不同的方式，那么解决此问题的方式个数为 $a_1\times a_2\times \dots \times a_n$。

容斥原理

当 $n=2$ 时，$|A\cup B|=|A|+|B|-|A\cap B|$

当 $n=3$ 时，$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

通项式：$|\bigcup_{i=1}^{n}A_i|=\sum_{\varnothing \neq J=\subseteq\{1,2,\dots,n\}}(-1)^{|J|-1}|\bigcap_{j\in J}A_j|$

德摩根定律

$\overline{A\cup B}=\overline{A}\cap \overline{B}$，$\overline{A\cap B}=\overline{A}\cup \overline{B}$

简记：交之补等于补之并，并之补等于补之交。

推论：$|\bigcap_{i=1}^{n}\overline{A_i}|=\sum_{\varnothing \neq J\subseteq \{1,2,\dots,n\}}(-1)^{|J|}|\bigcap_{j\in J} A_j|$

$$\begin{aligned} |\bigcup_{i=1}^{n}A_i|=\sum_{\varnothing \neq J=\subseteq\{1,2,\dots,n\}}(-1)^{|J|-1}|\bigcap_{j\in J}A_j|\\ |\bigcap_{i=1}^{n}\overline{A_i}|=\sum_{\varnothing \neq J\subseteq \{1,2,\dots,n\}}(-1)^{|J|}|\bigcap_{j\in J} A_j|\\ |\bigcap_{i=1}^{n}{A_i}|=\sum_{\varnothing \neq J\subseteq \{1,2,\dots,n\}}(-1)^{|J|}|\bigcap_{j\in J} \overline{A_j}| \end{aligned}$$

排列数 组合数

排列数：$A_{n}^{k}=\frac{n!}{(n-k)!}$

组合数：$C_{n}^{k}=\binom{n}{k}=\frac{A_{n}^{k}}{k!}=\frac{n!}{(n-k)!k!}=\frac{n\times(n-1)\times \dots \times (n-k+1)}{k!}=\frac{\prod_{i=0}^{k-1}{(n-i)}}{k!}$

特别地，若 $k>n$ 则 $A_{n}^{k}=C_{n}^{k}=0$。

性质：

1. $C_{n}^{0}=1$，$C_{n}^{1}=n$，$C_{n}^{2}=\frac{n(n-1)}{2}$

2. $C_{n}^{k}=C_{n}^{n-k}$

3. $C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}$

4. $\sum_{i=0}^{n}C_{n}^{i}=2^n$

求组合数

1. 暴力：

int C(int n,int k,int p){
    int a=1,b=1;
    F(i,0,k-1) a*=(n-i);
    F(i,1,k) b*=i;
    return (a/b)%p;
}

时间复杂度 $\mathcal{O}(Tn)$，但适用性极差（易爆 long long）。

2. 递推预处理：

$$C_{i,j}= \begin{cases} 1,j=0\\ C_{i-1,j}+C_{i-1,j-1},\text{otherwise} \end{cases}$$

由性质 $3$ 得证。

void InitC(int n,int p){
    F(i,0,n){
        C[i][0]=1;
        F(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    }
    return ;
}

时间复杂度 $\mathcal{O}(n^2+T)$。

3. 预处理阶乘+逆元：

这里使用了快速幂求逆元。

int C(int n,int k,int p){
    if (!k) return 1;
    return (fac[n]*ksm(fac[n-k],p-2,p)%p*ksm(fac[k],p-2,p)%p)%p;
}

时间复杂度 $\mathcal{O}(n+T\log p)$。

4. 卢卡斯定理：

见卢卡斯定理，仅限 $p$ 为质数时适用，时间复杂度 $\mathcal{O}(p+T\times \log n)$。

5. 扩展卢卡斯定理：

当 $p$ 不为质数时也适用，时间复杂度 $\mathcal{O}(p+T\log p)$。

二项式定理

$$(x+y)^{n}=C_{n}^{0}x^ny^0+C_{n}^{1}x^{n-1}y^{1}+\dots+C_{n}^{n}x^0y^n=\sum_{i=0}^{n}C_{n}^{i}x^{n-i}y^i$$

对于每一个 $(x+y)$，显然要么选 $x$，要么选 $y$。
若有 $k$ 个 $(x+y)$ 选择 $y$，则有 $n-k$ 个选择 $x$，由于要选取 $k$ 个 $(x+y)$，故系数为 $C_{n}^{k}$。
因为 $k$ 为分类，所以利用加法原理，得证。

计数技巧

等价替代

对于某些计数题，正面解决可能会很困难，这时可以用一些方法将问题转化为另一种更为容易计算的问题。

捆绑法

若要求某些物品相邻，则可将所需相邻的物品看做一个整体，然后计算排列，再分别计算每个整体内的排列相乘。

例题：有 $\text{ABCDE}$ 五种物品，其中要求 $\text{AB}$ 相邻，$\text{CD}$ 相邻，求排列方案数。

可先将 $\text{AB}$ 和 $\text{CD}$ 看作一个整体，然后对剩下的 $3$ 个物品进行排列，有 $A_{3}^{3}=6$ 种排列方案。
然后再计算各个整体内的排列，$A_{2}^{2}=2$ 种。
故共有 $2\times A_{2}^{2}\times A_{3}^{3}=24$ 种排列方案。

插空法

若要求某些物品两两不相邻，则可先将其它的物品排好，然后再从空当中插入，分别计算排列后相乘。

例题：有 $\text{ABCDEFG}$ 其中物品，其中要求 $\text{ABC}$ 两两不相邻，求排列方案数。

先对其它 $4$ 种物品进行排列，有 $A_{4}^{4}=24$ 种方案。
然后将剩下 $3$ 种物品插入到其中的 $5$ 个空当中，有 $A_{5}^{3}=60$ 种方案，故共有 $A_{4}^{4}\times A_{5}^{3}=1440$ 种排列方案。

隔板法

至少分配问题和不定方程整数解问题可转化为关于插板的组合问题。

例题 $1$：将 $n$ 个物品分给 $k$ 个人，要求每个人至少被分配到一个，求方案数。

将 $n$ 件物品排成一行，中间有 $k-1$ 个隔板，表示每个人分到的部分，而 $k-1$ 个隔板只能插入到 $n-1$ 个空当中，故方案数为 $C_{n-1}^{k-1}$。

例题 $2$：将例题 $1$ 的限制改为“允许有人被分配到 $0$ 个”，求方案数。

可将题意抽象为数学模型，求方程 $\sum_{i=1}^{k}x_i=n$ 的解，其中 $x_i\geq 1$。
若改限制为 $x\geq 0$，则设 $y_i=x_i+1$，转化为 $\sum_{i=1}^{k}=n+k$。
再结合上题的解，即可求出方案数为 $C_{n+k-1}^{k-1}$。

改变计数目标

对于某些计数题，直接解决可能会很困难，可以用减法原理或容斥原理等内容转化为容易求的问题。

改变枚举顺序

对于某些计数题，直接枚举只能拿到暴力分，可以改变枚举顺序使其更容易计算。

例题：求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\max(i,j)$。

$$\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\max(i,j) &=\sum_{k=1}^{n}k\sum_{i=1}^{n}\sum_{j=1}^{n}[\max(i,j)=k]\\ &=\sum_{k=1}^{n}k(2k-1)\\ &=2\sum_{k=1}^{n} k^2 -\frac{(n+1)n}{2}\\ &=\frac{4n^3+3n^2-n}{6} \end{aligned}$$

多重集的排列组合数

多重集：指包含重复元素的广义集合。

多重集的排列数

设 $S=\{n_1a_1,n_2a_2,\dots,n_ka_k\}$ 为多重集，则 $S$ 的全排列个数为

$$\frac{(\sum_{i=1}^{k} i)!}{\prod_{i=1}^{k}n_i!}$$

多重集的组合数

设 $S=\{n_1a_1,n_2a_2,\dots,n_ka_k\}$ 为多重集，从 $S$ 中取出 $r(r\leq \min(n_i))$ 个元素组成一个多重集，不考虑元素顺序，产生不同的多重集的数量为

$$C_{k+r-1}^{k-1}$$

设对于每一个 $a_i$ 选取 $x_i$ 个，则问题可转化为 $\sum_{i=1}^{k}x_i=r(x_i\geq 0)$ 的不定方程。
用隔板法求解即可。

卢卡斯定理

模数 $p$ 必须为质数。

$$C_{n}^{m}\bmod p=C_{\frac{n}{p}}^{\frac{m}{p}}\times C_{n\bmod p}^{m\bmod p}\bmod p$$

其中对于左半部分进行递归，右半部分直接进行计算，因为 $n\bmod p,m\bmod p\in [0,p-1]$。

时间复杂度 $\mathcal{O}(p+T\times \log n)$。

int fac[N],facinv[N];
void Init(int n,int p){
    fac[0]=1;
    F(i,1,n) fac[i]=fac[i-1]*i,fac[i]%=p;
    facinv[n]=ksm(fac[n],p-2,p);
    FJ(i,n-1,0) facinv[i]=facinv[i+1]*(i+1),facinv[i]%=p;
    return ;
}
int C(int n,int m,int p){
    if (m>n) return 0;
    return ((fac[n]*facinv[m])%p*facinv[n-m])%p;
}
int Lucas(int n,int m,int p){
    if (!m||n==m) return 1;
    return (Lucas(n/p,m/p,p)*C(n%p,m%p,p))%p;
}
int Solve(int n,int m,int p){
    Init(p-1,p);
    return Lucas(n,m,p);
}

卡特兰数

定义：一种常出现于各种计数问题的数列，记作 $H_n$，特别地，$H_0=H_1=1$。

卡特兰数列：

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$\dots$
$H_n$	$1$	$1$	$2$	$5$	$14$	$42$	$132$	$\cdots$

常见题型

1. $n$ 个左括号和 $n$ 个右括号组成的合法括号序列的数量？$H_n$。
2. 入栈序列为 $1,2,\dots,n$ 的合法出栈序列数量？$H_n$。
3. $n$ 个节点构成的不同的二叉树的数量？$H_n$。
4. 只能向上或向右走，能从 $(0,0)$ 走到 $(n,n)$ 且不接触直线 $y=x$ 的路线的数量？$2H_{n-1}$。
5. 只能向上或向右走，能从 $(0,0)$ 走到 $(n,n)$ 且不穿过直线 $y=x$ 的路线的数量？$H_{n+1}$。

求卡特兰数

以下所有公式均有 $i\geq 2$。

1. 递推：

$$H_i=\frac{H_{i-1}(4i-2)}{i+1}$$

2. 组合通式：

$$H_i=\frac{C_{2i}^{i}}{i+1}$$

$$H_i=C_{2i}^{i}-C_{2i}^{i-1}$$

$$H_i=\sum_{j=1}^{i}H_{j-1} H_{i-j}$$