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

· · 题解

实际上是同余方程组的合并

简述

如果给定n个同余方程组

\begin{cases} x &\equiv b_1 \pmod {a_1} \\ x &\equiv b_2 \pmod {a_2} \\ x &\equiv b_3 \pmod {a_3} \\ &\cdots \\ x &\equiv b_n \pmod {a_n} \\ \end{cases}

保证a是正整数，b是非负整数

现在要求找一个非负整数x，使得x最小且满足这n同余方程

数据保证x不超过10^{18}

题解

现在考虑合并两个同余方程的时候该怎么做

\begin{cases} x \equiv b \pmod {a} \\ x \equiv B \pmod {A} \end{cases}

这个可以写作

\begin{cases} x = ay + b \\ x = AY + B \end{cases}

由于x是一个常量，因此ay+b=AY+B，其中a,b,A,B都是常数

整理一下后就是ay+A(-Y)=B-b

通过exgcd，可以获得一组关于ay+A(-Y)=\gcd(a,A)的解(y_0,-Y_0)

即a(y_0 \times \frac{B-b}{\gcd(a,A)})+A(-Y_0 \times \frac{B-b}{\gcd(a,A)})=\gcd(a,A) \times \frac{B-b}{\gcd(a,A)}=B-b

由于x=ay+b，现在要最小化x，也就是最小化y，即最小化t=y_0 \times \frac{B-b}{\gcd(a,A)}

由于t的通解为t+\frac{A}{\gcd(a,A)}k，因此t的最小值为t_0=t \bmod \frac{A}{\gcd(a,A)}

于是就可以将这两个同余方程合并为

x \equiv a \times t_0+b \pmod {\mathbb{lcm}(a,A)}

代码

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N = 1e5 + 10;
ll x, y, d; int n;

void exgcd(ll &x, ll &y, ll a, ll b) {
    if(!b) d = a, x = 1, y = 0;
    else exgcd(y, x, b, a % b), y -= a / b * x;
}

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

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll a, b, A, B;

void merge() {
    exgcd(x, y, a, A);
    ll c = B - b;
    if(c % d) puts("-1"), exit(0);
    x = x * c / d % (A / d);
    if(x < 0) x += A / d;
    ll mod = lcm(a, A);
    b = (a * x + b) % mod; if(b < 0) b += mod;
    a = mod;
}

int main() {
    scanf("%d", &n);
    for(int i = 1 ; i <= n ; ++ i) {
        long long _A, _B;
        scanf("%lld%lld", &_A, &_B), A = _A, B = _B;
        if(i > 1) merge();
        else a = A, b = B;
    }
    printf("%lld\n", (long long)(b % a));
}