（扩展）中国剩余定理（模板）

中国剩余定理：猜数字

求解下列同余方程组（模数互质）

$\{\begin{array}{c}x\equiv a_1\left(mod{m}_1\right)\\ x\equiv a_2\left(mod{m}_2\right)\\ ⋮\\ x\equiv a_n\left(mod{m}_n\right)\end{array}$⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​x≡a1​ ( mod m1​ )x≡a2​ ( mod m2​ )⋮x≡an​ ( mod mn​)​

构造法
令： ${\displaystyle lcm=\prod _{i=1}^n{m}_i}$lcm=i=1∏n​mi​， ${\displaystyle M_i=\frac{lcm}{m_i}}$Mi​=mi​lcm​， $x=inv(M_i,m_i)$x=inv(Mi​,mi​)

则： ${\displaystyle ans=\sum _{i=1}^n{a}_i\ast x}$ans=i=1∑n​ai​∗x

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline ll read() {ll x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
 
const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

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

ll a[maxn], b[maxn];

int main() {
    int n=read();
    for(int i=1; i<=n; ++i) a[i]=read();
    ll lcm=1;
    for(int i=1; i<=n; ++i) b[i]=read(), a[i]=(a[i]%b[i]+b[i])%b[i], lcm*=b[i];
    ll ans=0, x, y;
    for(int i=1; i<=n; ++i) {
        ll tmp=lcm/b[i];
        exgcd(tmp,b[i],x,y);
        x=(x%b[i]+b[i])%b[i];
        ans=(ans+__int128(a[i])*x%lcm*tmp%lcm)%lcm; //__int128处也可以改为慢速乘
    }
    printf("%lld\n", ans);
}

扩展中国同余定理

处理模数不一定互质的情况

思路：不断合并同余方程

合并策略：

令： $g=(m_1,m_2)，m=lcm(m_1,m_2)$g=(m1​,m2​)，m=lcm(m1​,m2​)

${\displaystyle a=(inv(\frac{m_1}{g},\frac{m_2}{g})\ast \frac{a_2-a_1}{g})\%}$a=(inv(gm1​​,gm2​​)∗ga2​−a1​​)% ${\displaystyle \frac{m_2}{g}\ast m_1+a_1}$gm2​​∗m1​+a1​ $\left(modm\right)$( mod m )

详细证明

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

int n;
ll a[maxn], b[maxn];

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

ll exchina() {
    lll A=0, B=1, x, y; //A表示余数，B表示模数；a，b同理
    for(int i=1; i<=n; ++i) {
        lll g=exgcd(B,b[i],x,y);
        lll Bg=B/g, bg=b[i]/g;
        exgcd(Bg,bg,x,y);
        x=(x%bg+bg)%bg;
        lll lcm=Bg*b[i];
        if((a[i]-A)%g) return -1;
        A=(((a[i]-A)/g*x%bg*B+A)%lcm+lcm)%lcm;
        B=lcm;
    }
    return ll(A);
}

int main() {
    n=read();
    for(int i=1; i<=n; ++i) scanf("%lld%lld", &b[i], &a[i]);
    printf("%lld\n", exchina());
}