拓展中国剩余定理(EXCRT)

关于解决线型同余方程组的解

有两种不同的方法

CRT和拓展CRT

这里重点介绍一下拓展中国剩余定理

我们设前\(k - 1\)个方程的解是\(x'\),\(M = LCM_{i = 1}^{k - 1} b_i\)

则很明显,前\(k - 1\)个方程的通解是
\[ x' + tM \]
其中\(t\)为任意值

我们现在就要解决这样一个问题
\[ x' + tM \equiv a_i\pmod{b_i} \]
那么则有
\[ tM + hb_i = a_i-x' \]
这个直接\(exgcd\)就好了

注意这个时候我们的出来的解是
\[ tM +hb_i = gcd(M,b_i) \]
的解

所以我们求出\(t\)之后

真正的\(t\)应该是
\[ t/gcd(M,b_i) * (a_i-x') \]
这样我们就可以直接得出
\[ x = x'+tM \]
最后将\(b_i\)合并的\(M\)上就好了

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<ctime>
#define LL long long
#define pii pair<LL,LL>
#define mk make_pair
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 3;
LL a[N],b[N];
int n;
LL x,y;
inline LL exgcd(LL a,LL b){
    if(b == 0){
        y = 0;
        x = 1;
        return a;
    }
    LL r = exgcd(b,a % b);
    LL t = x;
    x = y;
    y = t - a / b * y;
    return r;
}
inline LL Mul(LL x,LL y,LL mod){
    LL res = 0;
    while(y){
        if(y & 1) res = (res + x) % mod;
        x = (x + x) % mod;
        y = y / 2;
    }
    return res;
}
inline LL excrt(){
    LL M = b[1];LL ans = a[1];
    for(int i = 2;i <= n;++i){
    //  printf("%d %lld %lld\n",i,M,b[i]);
        LL g = exgcd(M,b[i]);
    //  cout << g << endl;
        LL t = (a[i] - ans % b[i] + b[i]) % b[i]; 
        if(t % g != 0) return 0;
        x = Mul(x,t / g,b[i]); 
        ans += x * M;
        M = M * (b[i] / g);
        ans = ((ans % M) + M) % M;
    }
    return ans; 
}
int main(){
//  freopen("A.in","r",stdin);
    scanf("%d",&n);
    for(int i = 1;i <= n;++i) scanf("%lld%lld",&b[i],&a[i]);
    printf("%lld\n",excrt()); 
    return 0;
}   

另外请注意,在合并的时候可能炸\(LL\),所以尽量先除后乘