P4777题解

P4777 题解

2025.8.21 更正一处笔误。

题目链接

题意解释

给定

n

组非负整数

a_i,b_i

，求解关于

x

的方程组的最小非负整数解：

\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases}

数学前置知识

解方程：

\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n} \end{cases}

其中

a_1,a_2,\dots,a_n

两两互质。

我们可以构造

M=\prod_{i=1}^{n}{a_i}

并令

M_k=\frac{M}{a_k}

，

y_k

是

M_k

在模

a_k

意义下的逆元。

此时方程的解

x = \sum_{i=1}^{n}{a_i M_i y_i}

。

这便是中国剩余定理（CRT）。

但中国剩余定理有一个条件：要求

a_1,a_2,\dots,a_n

两两互质。

这也没有关系，我们可以任取

\begin{cases}x\equiv b_i\pmod{a_i}\\x\equiv b_j\pmod{a_j}\end{cases}

并计算出特解

x_0

，此时就会有通解

x=x_0-k \operatorname{lcm}(a_i,a_j)

，也就是说这两个方程会合并成一个方程

x\equiv x_0 \pmod{\operatorname{lcm}(a_i,a_j)}

，这便是扩展中国剩余定理的核心思想。

证明

取

\begin{cases}x\equiv b_i\pmod{a_i}\\x\equiv b_j\pmod{a_j}\end{cases}

。

转化成一般形式

\begin{cases}k_1 a_i+b_i=x\\k_2 a_j+b_j=x\end{cases}

。

移项得

k_1 a_i-k_2 a_j=b_j-b_i

。

此时我们已知

a_i,a_j,b_i,b_j

，但未知

k_1,k_2

。

将其看作关于

k_1,k_2

的不定方程，根据裴蜀定理，若

\gcd(a_i,a_j)\nmid(b_i-b_j)

，则方程无解。

对于有解的情况，用扩展欧几里得算法求出特解，并推出通解：

令

g=\gcd(a_i,a_j),d_1=\dfrac{a_i}{g},d_2=\dfrac{a_j}{g}

。

代入原方程得：

k_1 d_1 g-k_2 d_2 g=b_j-b_i

\because g\ne0\\\therefore k_1 d_1-k_2 d_2=\frac{b_j-b_i}{g}\\\because k_1 d_1-k_2 d_2\in\mathbb{Z}\\\therefore g\mid(b_j-b_i)

设特解为

\omega_1,\omega_2

，则

k_1,k_2

的特解为：

\begin{cases}k_1=\dfrac{b_j-b_i}{g}\omega_1\\k_2=-\dfrac{b_j-b_i}{g} \omega_2 \end{cases}

求得特解

x_0 = k_1 a_i+b_i=\dfrac{b_j-b_i}{g} \omega_1+b_i

。

原方程通解为

x=x_0-k\operatorname{lcm}(a_i,a_j),k\in \mathbb{Z}

。

证毕。

算法流程

初始化等价方程 $x \equiv 0\pmod{1}$ （即 $A=1, B=0$ ）
依次合并每个方程 $x \equiv b_i\pmod{a_i}$ $x \equiv b_{i} (mod a_{i})$ ：
- 计算 $g = \gcd(A,a_i)$ 。
- 用扩展欧几里得算法解 $A\cdot x+a_i\cdot y=g$ 。
- 若 $g\nmid(B-b_i)$ ，则无解。
- 计算特解 $x_0=B-A\cdot x\cdot\dfrac{B-b_i}{g}$ 。
- 更新模数 $A=\dfrac{A\cdot a_i}{g}$ 。
- 更新余数 $B=x_0\bmod A$ 。
最终解为 $B\bmod A$ （取最小非负整数）。

AC 代码

CPP

#include<bits/stdc++.h>
#define ll __int128 //数据量过大long long也不会溢出
using namespace std;
const int N=1e5+5,M=1e5+5;
int n;
ll A=1,B=0,x,y;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1,y=0;
		return a;
	}
	else{
		ll aa=exgcd(b,a%b,y,x);
		y-=a/b*x;
		return aa;
	}
}//扩展欧几里得算法
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
    	long long a,b;
		cin>>a>>b;
		ll gd=exgcd(A,a,x,y);
		x=(B-b)/gd*x;
		B=B-A*x;
		A=a/gd*A;
		B=(B%A+A)%A;
	}
	long long ans=(B%A+A)%A;
	cout<<ans<<"\n";
	return 0;
}

文章操作