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}。

证毕。

算法流程

  1. 初始化等价方程 x \equiv 0\pmod{1}（即 A=1, B=0）
  2. 依次合并每个方程 x \equiv b_i\pmod{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。
  3. 最终解为 B\bmod A（取最小非负整数）。

AC 代码

#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;
}