关于扩展中国剩余定理

扩展中国剩余定理：

$$ \left\{\begin{array}{l} a \equiv r_{1}\left(\bmod m_{1}\right) \\ a \equiv r_{2}\left(\bmod m_{2}\right) \end{array}\right. $$

我们想将上面的式子合并为一个。

上面的式子等价于：

$$ a=k_{1} m_{1}+r_{1}=k_{2} m_{2}+r_{2} $$

移项，则有：

$$ k_{1} m_{1}-k_{2} m_{2}=r_{2}-r_{1} $$

我们求出 $k_1$ 就能求出 $a$，$k_1 $可以扩欧求最小整数解。

求出 $k_1$ 之后，两个式子变合并为： $$ a \equiv k_1m_1+r_1\left(\bmod \operatorname{lcm}(m_1, m_2) \right) $$ 代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1,y=0;return a;}
    ll t=exgcd(b,a%b,x,y);ll tx=x,ty=y;
    x=ty,y=(tx-(a/b)*ty);return t;
}
void merge(ll &r1,ll &m1,ll r2,ll m2){
    ll k1,k2;ll d=exgcd(m1,m2,k1,k2);
    if((r2-r1)%d!=0) {cout<<-1;exit(0);}
    k1*=(r2-r1)/d,k2*=(r2-r1)/d;
    k1=(k1%(m2/d)+m2/d)%(m2/d);
    r1=k1*m1+r1;m1=m1/d*m2;
}
int main(){
    ll n,r1,m1;cin>>n>>m1>>r1;
    for(int i=2;i<=n;i++){
        ll r2,m2;
        cin>>m2>>r2;
        merge(r1,m1,r2,m2);
    }
    cout<<r1;
    return 0;
}