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

· · 题解

对于一组同余方程

\begin{cases} x \equiv a_1\ ({\rm mod}\ n_1) \\ x\equiv a_2\ ({\rm mod}\ n_2) \\ ... \\ x \equiv a_n\ ({\rm mod}\ n_n)\end{cases}

对于第一个和第二个式子

则有：

x = a_1 + k_1*n_1 x = a_2 + k_2*n_2

就有：

a_1 + k_1*n_1 = a_2 + k_2*n_2 k_1*n_1 - k_2*n_2 = a_2 - a_1

故我们设 d = a_2 - a_1 再变化一下形式就有：

k_1*n_1 + (-k_2)*n_2 = d

令 g = gcd(n_1,n_2)

这样我们就可以通过exgcd来求出一组解 x_1,y_1

满足 x_1*n_1 + y_2*n_2 = g

故：

x_1*d/g *n_1 + y_2*d/g*n_2 = g*d/g

则：

k_1 = x_1*d/g,k_2 = y_1*d/g

从而得到一组通解

k_1 = k_1 + n2/g*T k_2 = k_2 - n1/g*T

要使所求得的解最小且为正整数则可以根据 k_1 的通解形式求得

k_1 = (k_1\%(n_2/g) + n_2/g)\%(n_2/g)

*再带入 $x = a_1 + k_1n_1 得到 x$ **

令 A 为合并后的 a , N 为合并后的 n

*所以$N = lcm(n_1,n_2) = n_1 n_2 / g$**

根据x \equiv A\ ({\rm mod}\ N) 且 x 是满足该式子最小的值

得到：

A = x

欢迎来卡

#include<iostream>

typedef __int128 ll;

using namespace std;

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

bool flag = false;

ll a1,a2,n1,n2;

ll abs(ll x) {
    return x>0?x:-x;
} 

void china() {
    ll d = a2 - a1;
    ll g,x,y;
    exgcd(n1,n2,g,x,y);
    if (d % g == 0) {
        x = ((x*d/g)%(n2/g)+(n2/g))%(n2/g);
        a1 = x*n1 + a1;
        n1 = (n1*n2)/g;
    }
    else 
        flag = true;
}

int n;

long long as[100001];

long long ns[100001];

ll realchina() {
    a1 = as[0];
    n1 = ns[0];
    for (ll i = 1;i<n;i++) {
        a2 = as[i];
        n2 = ns[i];
        china();
        if (flag)
            return -1;
    }
    return a1;
}

int main() { 
    cin>>n;
    flag = false;
    for (ll i = 0;i<n;i++)
        cin>>ns[i]>>as[i];
    cout<<(long long)realchina()<<endl; 
}