预习心得 - CRT/exCRT

ExFish · 2025-07-04 09:24:52 · 算法·理论

一个求线性同余方程组的算法，如下：

CRT 定理在互质条件下的解法

当 m_i 两两互质，方程一定有解。并且在 0\sim(\prod m_i)-1 内有唯一解。可以理解为找到一个数 x，我们可以构造出一个解，然后每一次增加 (\prod m_i)-1 为一个循环，但不一定是最小的解。读者自证不难，这里给出构造方法如下：

我们先考虑构造 m 组方程，其中第 i 组存在一个 m_i=1，其余 m_i=0。我们可以解出一些最小解，设为 x_i。然后我们设 M=\prod m_i，答案就是 \sum x_im_i \bmod M。我们有余数的可乘性与可加性，把这些方程的解加起来，相当于构造了一些拆开每一个 m_i 的方程，解出来，加回去就是原方程。

在不互质条件下的解法

我们可以考虑通过原有方程推出一个其他的同余方程，不停消除方程，就会出现最后的线性同余方程。代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
void crt(ll &a,ll &b,ll c,ll d){
    if(a==-1&&b==-1)
        return;
    ll x,y;
    ll g=exgcd(b,d,x,y);
    if((c-a)%g!=0){ // No Solution.
        a=-1,b=-1;
        return;
    }
    d/=g;
    ll t0=((c-a)/g%d*x%d+d)%d;
    a=b*t0+a,b=b*d;
}
int n;
ll a,b,c,d;
void solve(){
    cin>>n;
    a=0,b=1;
    for(int i=1;i<=n;i++){
        cin>>d>>c;
        crt(a,b,c,d);
    }
    cout<<a<<"\n";
}
signed main(){
    solve();
    return 0;
}