【学习笔记】扩展中国剩余定理（exCRT）

前言

扩展中国剩余定理（exCRT）适用于求解模线性方程组，且模数不一定两两互质的情况

求解

两个方程

先考虑只包含两个方程的模线性方程组：
\begin{cases} x\equiv b_1\pmod{a_1}\\ x\equiv b_2\pmod{a_2} \end{cases}
其中 a_1,a_2 不一定互质

模线性方程组等价于二元一次不定方程组：
\begin{cases} x=a_1 k_1+b_1\\ x=a_2 k_2+b_2 \end{cases}
联立并移项，得：a_1 k_1-a_2 k_2=b_2-b_1，且该方程有解的充要条件为 \mathrm{gcd}(a_1,a_2)|(b_2-b_1)

如果该方程无解，则原方程组也无解；否则可以解得 k_1,k_2，且原方程组的一个特解为 x_0=a_1 k_1+b_1，通解即为 x=x_0+t\cdot\mathrm{lcm}(a_1,a_2)，其中 t 为任意整数

多个方程

对于只包含两个方程的模线性方程组，由其通解形式可得，该方程组等价于同余方程 x\equiv x_0\pmod{\mathrm{lcm(a_1,a_2)}}，这样就将原来的两个同余方程等价转化为了一个同余方程

对于包含多个方程的模线性方程组，求解的方法就是：将方程不断地等价合并，直到只剩下一个方程为止。如果中途出现了无解的情况，则原方程组也一定无解

总复杂度 O(n\log a)

Code

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

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005
#define int __int128_t

using namespace std;

int n;
int a[MAX_N];
int b[MAX_N];

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

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

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

int excrt(int *a, int *b, int n) {
    int x, y, A = a[1], B = b[1];
    for (int i = 2; i <= n; i++) {
        int g = gcd(A, a[i]);
        if ((b[i] - B) % g) {
            return -1;
        }
        exgcd(A, a[i], x, y);
        int t = a[i] / g;
        x = (((b[i] - B) / g * x) % t + t) % t;
        B = A * x + B;
        A = lcm(A, a[i]), B %= A;
    }
    return B;
}

signed main() {
    long long x, y;
    scanf("%lld", &x);
    n = x;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &x, &y);
        a[i] = x, b[i] = y;
    }
    printf("%lld\n", (long long)excrt(a, b, n));
}