时间

• $2025/02/05-2025/02/10$

---

最优化

• $2025/02/06$

---

---

初等数论

• $2025/02/07$

---

斐蜀定理（Bézout's lemma）

定理 1.1

对于两个整数 $a$ 和 $b$，有整数 $x$ 和 $y$ 使得 $ax+by=gcd(a,b)$。

推论

整数 $a$ 与 $b$ 互素当且仅当存在整数 $x$ 和 $y$ 使得 $ax+by=1$。

证明

运用辗转相除法去证明。

假设 $d=gcd(a,b)$，那么 $d$ 必然是辗转相除后最后的一个非零的余数：

$$\begin{array}{rl}a& =b\cdot q_1+r_1\\ b& =r_1{q}_2+r_2\\ r_1& =r_2{q}_3+r_3\\ & \dots \\ r_{n-2}& =r_{n-1}{q}_n+d\end{array}$$

由上面所述我们可以知道：

$$\begin{array}{rl}{r}_1& =a-b{q}_1\\ r_2& =b-r_1{q}_2\\ & =b-(a-b_1)q_2\\ & =b-a{q}_2+b{q}_1{q}_2\\ & =-a{q}_2+b(q_1{q}_2+1)\\ & \dots \end{array}$$

综上，推到最后发现所有的 $r$ 都可以表示为 $ax+by=r$ 的形式，也就是说明 $ax+by=d$ 成立。

还可以换种方式去理解斐蜀定理：

对于 $\mathrm{\forall }x,y$，$d=ax+by$，$d$ 一定是 $gcd(a,b)$ 的整数倍；最小的 $d$ 是 $gcd(a,b)$。

---

【模板】裴蜀定理

对于两对数 $(p,q)$ 的情况，$A_p\times X_p+A_q\times X_q$ 的写法很类似于 $ax+by$。根据斐蜀定理，有整数 $x$ 和 $y$ 使得 $ax+by=gcd(a,b)$，也就是其最小值为 $|gcd(a,b)|$，不断合并即可。

---

线性丢番图方程

定义

方程 $ax+by=c$ 称为二元线性丢番图方程，其中 $a,b,c$ 为已知整数，$x,y$ 是变量，问是否有整数解。

实际上就是在二维 $x—y$ 平面上的一条直线，这条直线上如果有整数坐标点，方程就有解；如果没有整数坐标点，就无解。如果存在一个解，就有无穷多个解。

定理 2.1

对于整数 $a$ 和 $b$，$d=gcd(a,b)$。

方程 $ax+by=c$ 有解的充分必要条件是 $d\mid c$。

若知道方程的一个特解为 $(x_0,y_0)$，则通解为 $x=x_0+\frac{b}{d}\times k,y=x_0+\frac{a}{d}\times k$，其中 $k$ 为任意整数。

证明

两边同时除以 $d$，则左边必然是整数，若想要式子成立，右边必然也需要时整数，所以 $d\mid c$。

在 $a{x}_0+b{y}_0=d$ 特解的基础上，寻找通解 $a(x_0+mk)+b(y_0+nk)=d$（其中 $k$ 为任意整数）：

拆式子，得 $a{x}_0+amk+b{y}_0+bnk=d$；

等价移项并消掉 $d$，得到 $amk+bnk=0$；

构造 $m,n$ 使得等式成立：

$\{\begin{array}{l}m=\frac{b}{d}\\ n=-\frac{a}{d}\end{array}$

$a\times \frac{b}{d}\times k+b\times (-\frac{a}{d})\times k=\frac{abk}{d}-\frac{abk}{d}=0$。

综上所述，可以知道：

$\{\begin{array}{l}x=x_0+\frac{b}{d}\times k\\ y=y_0-\frac{a}{d}\times k\end{array}$

---

扩展欧几里得（exgcd）

求解方程 $ax+by=c$ 关键在于找到一个特解，由斐蜀定理可以知道 $ax+by=d$ 必定有整数解，那么尝试使用扩展欧几里得算法求一个特解 $(x_0,y_0)$。

当前层为 $(a,b,x,y)$，这里 $a>b$，对于 $ax+by=d$，假设 $a=bq+r$，那么：

$$\begin{array}{rl}(bq+r)x+by& =d\\ bqx+rx+by& =d\\ b(qx+y)+rx& =d\end{array}$$

下一层就要求解 $b(qx+y)+rx=d$，按照辗转相除，状态应该为 $(b,a\mathrm{\%}b,y,x)$，设得到的解是 $(x^{\prime },y^{\prime })$，则：

$\{\begin{array}{l}x=y^{\prime }\\ qx+y=x^{\prime }\end{array}$

移一下项：

$\{\begin{array}{l}x=y^{\prime }\\ y=x^{\prime }-qx\end{array}$

到最后 $b=0$ 时，那这时候 $x=1,y=0$ 就是解。

最后求出来特解为 $(x_0^{\prime },y_0^{\prime })$，那么 $ax+by=c$ 的特解为：

$\{\begin{array}{l}{x}_0=x_0^{\prime }\times \frac{c}{d}\\ y_0=y_0^{\prime }\times \frac{c}{d}\end{array}$

注意程序自定义函数中的 $x$ 和 $y$ 需要引用！！！

Code

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

---

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

对于方程 $ax+by=c$，先用婓蜀定理判断方程是否有解，若无解，则输出 $-1$。

我们由定理2.1可知：

$\{\begin{array}{l}x=x_0+\frac{b}{d}\times k\\ y=y_0-\frac{a}{d}\times k\end{array}$

当 $k$ 增大时，$x$ 变大，$y$ 变小。

设 $\frac{a}{d}$ 为 $d_x$，$-\frac{a}{d}$ 为 $d_y$，也就是说：

$\{\begin{array}{l}x=x_0+d_x\times k\\ y=y_0-d_y\times k\end{array}$

接下来寻找 $x$ 的最小正整数解 $x_{min}$，那么 $x_{min}\ge 1$，即 $x_0-d_x\ge 1$；

解一元一次不等式，得 $k\le \lceil \frac{1-x_0}{d_x}\rceil$，注意这里是大于等于，所以要向上取整；

$k$ 取到最大值有 $x_{min}$，所以 $x_{min}=x_0-\lceil \frac{1-x_0}{d_x}\rceil$。

那很明显的，在所有的正整数解（很重要，没有这个前提条件的话不一定成立）之中 $x_{min}$ 对应的是 $y_{max}$，接下来考虑求 $x_{max}$ 和 $y_{min}$；

由于 $y$ 的通解为 $y=y_0-d_{y}k$，已知 $y_{max}$，那么 $y_{min}=y_{max}mod{d}_y$，由于要避免取模出来有 $0$，则 $y_{min}=(y_{max}-1)mod{d}_y+1$。

在所有正整数解中，$y_{max}$ 对应的是 $x_{min}$，易知从 $x_{min}$ 到 $x_{max}$ 同 $y_{max}$ 到 $y_{min}$ 中 $k$ 的增减量是一样的，是 $\frac{y_{max}-1}{d_y}$，这也是正整数解的数量，因为在这个过程中，$x$ 和 $y$ 都一直保持 $>0$，那么 $x_{max}=x_{min}+\frac{y_{max}-1}{d_y}\times d_x$。

---

同余

定义

设 $m$ 为正整数，若 $a$ 和 $b$ 是整数，且 $m\mid (a-b)$，则称 $a$ 和 $b$ 模 $m$ 同余。

也可以说成 $a$ 除以 $m$ 得到的余数，和 $b$ 除以 $m$ 的余数相同；或者说 $a-b$ 除以 $m$，余数为 $0$。

把 $a$ 和 $b$ 模 $m$ 的同余记为 $a\equiv b(\mathrm{mod}m)$。

性质

同余的基本概念：若 $a$ 和 $b$ 为整数，$m$ 为正整数，则 $a\equiv b(\mathrm{mod}m)$ 当且仅当 $amodm=bmodm$。

将其转化为等式：其成立当且仅当存在整数 $k$ 使得 $a=b+km$。这也说明了同余方程和线性丢番图方程的关系。

模 $m$ 的同余满足以下基本性质：

• 自反性：若 $a$ 为整数，则 $a\equiv a(\mathrm{mod}m)$；

• 对称性：若 $a,b$ 为整数，且 $a\equiv b(\mathrm{mod}m)$，则 $b\equiv a(\mathrm{mod}m)$；

• 传递性：若 $a,,c$ 为整数，且 $a\equiv b(\mathrm{mod}m)$ 和 $b\equiv c(\mathrm{mod}m)$，则 $a\equiv c(\mathrm{mod}m)$。

同余的加简乘除：

若 $c$ 是整数，且 $c\equiv d(\mathrm{mod}m)$。

• 同加性：$a+c\equiv b+d(\mathrm{mod}m)$；

• 同减性：$a-c\equiv b-d(\mathrm{mod}m)$；

• 同乘性：$a\times c\equiv b\times d(\mathrm{mod}m)$；

• 无同除性：同余的两边同时除以一个整数，不一定保持同余；

• 同幂性：若 $a,b,k$ 和 $m$ 是整数，$k,m>0$，且 $a\equiv b(\mathrm{mod}m)$，则 $a^k\equiv b^k(\mathrm{mod}m)$

定理 4.1

$a,b$ 和 $m$ 为整数，$m>0$，设 $d=gcd(a,m)$。

若 $d$ 不能整除 $b$，则同余方程 $a\equiv b(\mathrm{mod}m)$ 无解；反之，$d\mid b$，则有 $d$ 个不同余的解。

前半部分可以理解为 $a\equiv b(\mathrm{mod}m)$ 有解的充分必要条件是 $d\mid b$。

证明

前半部分很好理解，把这个同余方程转换为等式：$ax+my=b$，再运用定理 2.1，可得这个等式有解，条件是 $d\mid b$；

同样的对于等式去求出特解 $(x_0,y_0)$ 的通解，$x=x_0+\frac{m}{d}\times k$，但是这里是同余方程，$k$ 是有范围的，当 $0\le k<d$ 有 $d$ 个模 $m$ 的不同余解。利用剩余系的概念解释，$k$ 取遍了模 $d$ 的完全剩余系。

注意：$x_0,y_0$ 不一定是最小的解！！！

推论

当 $a$ 和 $m$ 互素的时，因为 $d=1$，所以线性同余方程 $ax\equiv b(\mathrm{mod}m)$ 有唯一的模 $m$ 不同余解。

回到求解 $ax\equiv b(\mathrm{mod}m)$ 中未知数 $x$ 的问题，首先求逆元，然后利用逆元求得 $x$。

---

[NOIP 2012 提高组] 同余方程

这题相当于在求整数 $a$ 在模 $b$ 意义下的逆元，不保证 $a$ 和 $b$ 互素，并不能使用费马小定理去解决问题；

将 $ax\equiv 1(\mathrm{mod}b)$ 转化为等式方程 $ax+by=1$，尝试用扩展欧几里得求解出这个方程的一个特解 $(x_0,y_0)$，通解是 $x=x_0+bk$，然后通过取模计算得出最小整数解。

青蛙的约会

假设跳的次数为 $t$，则 $x-y=(n-m)t+Lk$，其中 $k$ 为任意整数。

设 $n-m=a,t=x^{\prime },L=b,k=y^{\prime },x-y=c$，那么就是 $a{x}^{\prime }+b{y}^{\prime }=c$，用扩展欧几里得求出特解 $x_0$ 像上面取模计算得出最小整数解即可。

---

中国剩余定理（Chinese Remainder Theorem, CRT）

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

引入

「物不知数」问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即求同时满足以下条件的整数：除以 $3$ 余 $2$，除以 $5$ 余 $3$，除以 $7$ 余 $2$。

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。

$2\times 70+3\times 21+2\times 15=233=2\times 105+23$，故解为 $23$。

定理 5.1

有 $m_1,m_2,\dots ,m_r$ 这 $r$ 个两两互素的正整数，则同余方程组：

$$\begin{array}{rl}x& \equiv a_1(\mathrm{mod}{m}_1)\\ x& \equiv a_2(\mathrm{mod}{m}_2)\\ & \dots \\ x& \equiv a_k(\mathrm{mod}{m}_r)\end{array}$$

有整数解，并且模 $M=\prod _{i=1}^r{m}_i$ 唯一，解为：

$$x\equiv (a_1{M}_1{M}_1^{-1}+a_2{M}_2{M}_2^{-1}+\cdots +a_r{M}_r{M}_r^{-1})(\mathrm{mod}M)$$

其中 $M_i=\frac{M}{m_i}$，$M_i^{-1}$ 为 $M_i$ 在模 $m_i$ 下的逆元。

证明

设 $c_i=M_i{M}_i^{-1}$（不对 $m_i$ 取模），我们需要证明对于所有 $i,i\in [1,r]$ 都能满足 $x\equiv a_i(\mathrm{mod}{m}_i)$。

对于任意 $i,j$ 且 $i\ne j$，都有 $M_j\equiv 0(\mathrm{mod}{m}_i)$，因为 $M_j=\frac{M}{m_j},M=\prod _{i=1}^r{m}_i$，也就是 $M_j$ 的所有乘数中 $m_i$，同余方程成立；

故也有 $c_j\equiv M_j\equiv 0(\mathrm{mod}{m}_i)$。又因为 $m_i$ 两两互素，有 $c_i\equiv M_i(M_i^{-1}mod{m}_i)\equiv 1(\mathrm{mod}{m}_i)$，所以：

$$\begin{array}{rlr}x& \equiv \sum _{k=1}^r{a}_k{c}_k& (\mathrm{mod}{m}_i)\\ & \equiv a_i{M}_i(M_i^{-1}mod{m}_i)& (\mathrm{mod}{m}_i)\\ & \equiv a_i& (\mathrm{mod}{m}_i)\end{array}$$

另外，若 $x\ne y$，总存在 $i$ 使得 $x$ 和 $y$ 在模 $m_i$ 下不同余，故系数列表 $\{a_i\}$ 与 $x$ 是一一映射关系，方程组总是有唯一的解。

注意：有可能会爆long long，这里使用__int128来代替，输入输出要用快读快输。

Code

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N=22;
inline int read() {
    int x=0;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) ;
    for(;isdigit(c);c=getchar())
        x=x*10+c-48;
    return x;
}
inline void write(int x) {
    if(x>9)
        write(x/10);
    putchar(x%10+48);
    return ;
}
int n,a[N],b[N];
inline int exgcd(int a,int b,int &x,int &y) {
    if(b==0) {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
inline int CRT(int a[],int m[],int n) {
    int p=1,M[N];
    for(int i=1;i<=n;i++)
        p*=m[i];
    for(int i=1;i<=n;i++)
        M[i]=p/m[i];
    int X=0;
    for(int i=1;i<=n;i++) {
        int x,y;
        int d=exgcd(M[i],m[i],x,y);
        x=(x%m[i]+m[i])%m[i]; 
        X=(X+a[i]*M[i]%p*x%p)%p;
    }
    return X;
}
signed main() {
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=read();
    write(CRT(b,a,n));
    return 0;
}

---

扩展中国剩余定理（EXCRT）

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

引入

上文所讲到的中国剩余定理的前提是所有的 $m$ 是两两互素的，那么若模数 $m$ 两两不互素怎么办呢？

实现

使用迭代法，每次合并两个同余式子，逐步操作，直到最后合并完所有式子，只剩下一个，就是最后的答案。

$$\begin{array}{rl}x& \equiv a_1(\mathrm{mod}{m}_1)\\ x& \equiv a_2(\mathrm{mod}{m}_2)\\ & \dots \\ x& \equiv a_k(\mathrm{mod}{m}_r)\end{array}$$

从头开始，将同余方程转为丢番图方程的形式：

$$\begin{array}{r}x=a_1+X{m}_1\\ x=a_2+Y{m}_2\end{array}$$

合并两个等式：

$$a_1+X{m}_1=a_2+Y{m}_2$$

移项：

$$X{m}_1+(-Y)m_2=a_2-a_1$$

用扩展欧几里得去求得一个特解 $X_0$，很显然，在取模下，$X$ 的解是唯一的，且是非负整数，那么就有：

$$X=(X_{0}c/d)modb/d$$

这里区分一下，数学上的 $mod$ 正整数的结果是非负整数；然而在程序运行中，负整数取模正整数数是负整数，所以需要加上模数再取模！！

将 $X$ 代回 $x=a_1+X{m}_1$ 中求得原等式的一个特解 $x^{\prime }$，合并后新的等式为：

$$x=a+Xm$$

即：

$$x\equiv a(\mathrm{mod}m)$$

其中 $m=\frac{m_1{m}_2}{gcd(m_1,m_2)},a=x^{\prime }$，再细细品味其中的妙处。

新的 $m$ 的求解就很好说明了在普通中国剩余定理中的 $M=\prod _{i=1}^r{m}_i$，所有 $m_i$ 互素，所以最小公约数为 $1$，可以省略掉，蕴含的思想是由特殊到一般？...

Code

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N=1e5+10;
inline int read() {
	int x=0;
	int c=getchar();
	for(;!isdigit(c);c=getchar()) ;
	for(;isdigit(c);c=getchar())
		x=x*10+c-48;
	return x;
}
inline void write(int x) {
	if(x>9)
		write(x/10);
	putchar(x%10+48);
	return ;
} 
int n,a[N],b[N],x,y;
inline int exgcd(int a,int b,int &x,int &y) {
	if(b==0) {
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
inline int mul(int a,int b,int m) {
	int res=0;
	while(b) {
		if(b&1)
			res=(res+a)%m;
		a=(a+a)%m,b>>=1;
	}
	return res;
}
signed main() {
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=read();
	if(n==1) {
		int A=1,B=a[1],C=b[1];
		int d=exgcd(A,B,x,y);
//		if(C%d!=0) {
//			printf("-1\n");
//			return 0;
//		}
		x=(x*(C/d)%(B/d)+(B/d))%(B/d);
		write(x);
		return 0;
	}
	int a1=b[1],m1=a[1],ans;
	for(int i=2;i<=n;i++) {
		int a2=b[i],m2=a[i];
		int A=m1,B=m2,C=((a2-a1)%m2+m2)%m2;
		int d=exgcd(A,B,x,y);
//		if(C%d!=0) {
//			printf("-1\n");
//			return 0;
//		}
//		x=mul(x,C/d,B/d);
		x=(x*(C/d)%(B/d)+(B/d))%(B/d);
		ans=(a1+x*m1);
		m1=m1*m2/d;
		ans=(ans%m1+m1)%m1;
		a1=ans;
	}
	write(ans);
	return 0;
}

---

卢卡斯定理（Lucas）

【模板】卢卡斯定理/Lucas 定理

引入

求组合数的方法有很多种，其中用逆元的求法，是通过 $C_n^{r}modm=\frac{n!}{r!(n-r)!}modm$，但是若 $m$ 小于 $n$，那就不能保证 $r!$ 和 $(n-r)!$ 在模 $m$ 下有逆元了；然而用杨辉三角的话，时间复杂度为 $O(n^2)$，不够优秀，那么我们就需要用到卢卡斯定理了！！！

定理

对于非负整数 $n,r$ 和素数 $m$，有：

$$C_n^r\equiv \prod _{i=0}^k{C}_{n_i}^{r_i}(\mathrm{mod}m)$$

其中，$n=\sum _{i=0}^k{n}_i{m}^i$ 和 $r=\sum _{i=0}^k{r}_i{m}^i$，相当于是把 $n$ 和 $r$ 表示为 $k$ 位的 $m$ 进制数，对每位分别进行计算组合数，最后乘起来。

编程时的卢卡斯定理表达：

$$C_n^r\equiv C_{nmodm}^{rmodm}\times C_{\lfloor n/m\rfloor }^{\lfloor r/m\rfloor }(\mathrm{mod}m)$$

证明

对于素数 $m,r\in (0,m)$，有：

$$C_m^r=\frac{m!}{r!(m-r)!}=\frac{(m-1)!}{(r-1)!(m-r)!}\times \frac{m}{r}=C_{m-1}^{r-1}\times \frac{m}{r}\equiv 0(\mathrm{mod}m)$$

也可以这样理解，因为 $C_m^r$ 为整数，$r$ 和 $m-r$ 取不到 $m$，所以 $m!$ 必然进行运算后必然会剩下一个 $m$，所以在模 $m$ 的意义下与 $0$ 同余。

在上面的条件中 $r$ 是不能取到 $0$ 和 $m$ 的，因为 $C_m^0$ 和 $C_m^m$ 的组合数为 $1$，$1\not\equiv 0(\mathrm{mod}m)$。

带入二项式定理中，得到：

$$\begin{array}{rl}(1+x{)}^m& =\sum _{r=0}^m{C}_m^r\times x^r\\ & =1+\sum _{r=1}^{m-1}{C}_m^r+x^m\\ & \equiv 1+x^m& (\mathrm{mod}m)\end{array}$$

令 $n=qm+a$，有：

$$\begin{array}{rl}(1+x{)}^n& =(1+x{)}^{qm+a}\\ & =(1+x{)}^{qm}(1+x{)}^a\\ & \equiv (1+x^m{)}^q(1+x{)}^a& (\mathrm{mod}m)\\ & \equiv (\sum _{i=0}^q{C}_q^i\times x^i)\times (\sum _{j=0}^a{C}_a^j\times x^j)& (\mathrm{mod}m)\end{array}$$

若 $r>m$，则 $C_r^m=0$，那么我们可以把式子等价换成：

$$\sum _{r=0}^n{C}_n^r\times x^r\equiv (\sum _{i=0}^q{C}_q^i\times x^i)\times (\sum _{j=0}^{m-1}{C}_a^j\times x^j)(\mathrm{mod}m)$$

其中需要保证 $im+j\le n$。

这里为什么要把 $a$ 换成 $m-1$ 呢？

其实就可以把左边的 $r\in [0,n]$ 在右边用所有数表示了，即 $r=im+j$，更便于理解。

最后将两边第 $x^r$ 次的系数取出来，根据 $r=im+j,i=\lfloor r/m\rfloor ,j=rmodm,a=nmodm,q=\lfloor n/m\rfloor$，那就是：

$$\begin{array}{rlr}{C}_n^r& \equiv C_q^i\times C_a^j& (\mathrm{mod}m)\\ & \equiv C_{\lfloor n/m\rfloor }^{\lfloor r/m\rfloor }\times C_{nmodm}^{rmodm}& (\mathrm{mod}m)\end{array}$$

最后展开利用递归实现，时间复杂度瓶颈在预处理求逆元部分，为 $O(nlogn)$，其实可以优化预处理，考场再用吧...

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int T,a,b,m,fac[N],inv[N];
inline int qpow(int a,int p) {
    int res=1;
    while(p) {
        if(p&1)
            res=res*a%m;
        a=a*a%m,p>>=1;
    }
    return res;
}
inline void init_() {
    fac[0]=inv[0]=1;
    for(int i=1;i<N;i++)  {
        fac[i]=fac[i-1]*i%m;
        inv[i]=inv[i-1]*qpow(i,m-2)%m;
    }
    return ;
}
inline int C(int n,int r) {
    if(r>n)
        return 0;
    return fac[n]*inv[n-r]%m*inv[r]%m;
}
inline int Lucas(int n,int r,int m) {
    if(r==0)
        return 1;
    return C(n%m,r%m)*Lucas(n/m,r/m,m)%m;
}
signed main() {
    scanf("%lld",&T);
    while(T--) {
        scanf("%lld%lld%lld",&a,&b,&m);
        init_();
        printf("%lld\n",Lucas(a+b,a,m));
    } 
    return 0;
}

---