中国剩余定理（CRT）

中国剩余定理可以用来求解下面的线性同余方程组 $\left\{\begin{array}{c} x \equiv r_{1}\left(\bmod m_{1}\right) \\ x \equiv r_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv r_{n}\left(\bmod m_{n}\right) \end{array}\right.$ $其中模数 m_{1}, m_{2}, \cdots, m_{n} 为两两互质的整数, 求 x 的最小非负整数解。$ 做法如下：

1. 计算所有的模数的积为M
2. 计算第i个方程的$c_i=\frac{M}{m_i}$
3. 求$c_i$再模$m_i$下的逆元$c_i^{-1}$
4. $x=\sum_{i=1}^{n}{r_ic_ic_i^{-1}}(\bmod M)$

题目链接：https://www.luogu.com.cn/problem/P1495

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 20;

int n;
LL m[N],r[N];


LL exgcd(LL a,LL b,LL &x,LL &y){
    if (b==0){
        x=1,y=0;
        return a;
    }
    LL x1,y1,d;
    d= exgcd(b,a%b,x1,y1);
    x=y1,y=x1-a/b*y1;
    return d;
}

LL CRT(LL m[],LL r[]){
    LL M=1,ans=0;
    for(int i=1;i<=n;i++) M*=m[i];
    for(int i=1;i<=n;i++){
        LL c=M/m[i],x,y;
        exgcd(c,m[i],x,y);
        //x为c的乘法逆元
        ans=(ans+r[i]*c*x%M)%M;
    }
    return (ans%M+M)%M;//这样是为了求最小非负整数解
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin>>n;
    for(int i=1;i<=n;i++) cin>>m[i]>>r[i];
    pr(CRT(m,r))

    return 0;
}