题解：P4777 【模板】扩展中国剩余定理（EXCRT）

· · 题解

扩展中国剩余定理 exCRT

算法介绍

要想学会扩展中国剩余定理，要先学会 exgcd，至于中国剩余定理，这并不重要。

中国剩余定理给了你一个一元线性同余方程组：

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

让你求出 x 的最小非负整数解，在中国剩余定理中，给了你 a_1 \sim a_n 互质的条件，但扩展中国剩余定理没有，我们考虑如何解决。

注意到，我们难以直接算出 x 的最小非负整数解，所以我们考虑把这些同余方程组两两合并，我们考虑如何求出如下同余方程组：

\begin{cases}x\equiv x_1\pmod{y_1}\\x\equiv x_2\pmod{y_2}\\\end{cases}

扩展中国剩余定理告诉我们，它们可以合并成一个同余方程：

x\equiv x_1 - y_1 \times a\pmod{\operatorname{lcm}(y_1,y_2)}

然后以此类推，两两合并，直到合并成一个方程，我们就求出了原方程组的解。接下来我们考虑如何证明它。

正确性证明

把同余方程写成等式：

x_1 = y_1 \times k_1 + x \\ x_2 = y_2 \times k_2 + x

可以得出：

x_1 - y_1 \times k_1 = x_2 - y_2 \times k_2

整理式子：

y_1 \times k_1 - y_2 \times k_2 = x_1 - x_2

这样我们就把它写成了二元一次方程组，于是我们可以用 exgcd 求出 y_1 \times k_1 - y_2 \times k_2 = \gcd (y_1,y_2) 的解，我们令其为 a 与 b。

那么原二元一次方程组的解为：

k_1 = a + \frac{y_2}{\gcd (y_1,y_2)} \times k \\ k_2 = b - \frac{y_1}{\gcd (y_1,y_2)} \times k

根据前文，我们知道：

x = x_1 - y_1 \times (a + \frac{y_2}{\gcd (y_1,y_2)} \times k)

展开一下：

x = x_1 - y_1 \times a + y_1 \times \frac{y_2}{\gcd (y_1,y_2)} \times k \\ x = x_1 - y_1 \times a + \frac{y_1 \times y_2}{\gcd (y_1,y_2)} \times k

我们都知道，a \times b = \gcd (a,b) \times \operatorname{lcm}(a,b)，那我们的式子可以改写成：

x = x_1 - y_1 \times a + \operatorname{lcm}(y_1,y_2) \times k

然后我们把它再次转换成同余方程，把我们设的 k 换成同余方程：

x\equiv x_1 - y_1 \times a\pmod{\operatorname{lcm}(y_1,y_2)}

这样，我们就证明完了我们上面给出的那个式子。

然后，我们就可以写代码了。

代码实现

注意计算过程可能会爆 long long，记得开 int128。

#include<bits/stdc++.h>
#define int __int128//计算过程可能会爆 long long
#define code using
#define by namespace
#define dong0717 std;
code by dong0717
int x,y;
int exgcd(int a,int b){//exgcd模板
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b);
    int t=x;
    x=y;
    y=t-a/b*y;
    return d;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    long long n;
    cin>>n;
    int a1=1,b1=0;
    for(int i=1;i<=n;i++){
        long long a2,b2;
        cin>>a2>>b2;
        int d=exgcd(a1,(__int128)a2);
        x=(b1-b2)/d*x;
        b1-=a1*x;
        a1=a2/d*a1;
        b1=(b1%a1+a1)%a1;
    }
    cout<<(long long)((b1%a1+a1)%a1);
    return 0;
}