莫欺少年穷，修魔之旅在这开始—>算法提高课题解

中国剩余定理

$a_1,a_2,…,a_n\ 两两互质$

$\begin{cases}x\equiv b_1\pmod{a_1}\\\\x\equiv b_2\pmod{a_2}\\\\\ \quad \vdots\\\\x\equiv b_n\pmod{a_n}\end{cases}$

过程：

$1.\ 计算所有模数的积\ M$

$2.\ 对于第\ i\ 个方程\\\\ \ \ \ \ a.计算\ M_i=\dfrac{M}{a_i}\\\\ \ \ \ \ b.计算\ M_i\ 在模\ a_i\ 意义下的逆元\ t_i，即\ M_it_i\equiv1\pmod{a_i}\Rightarrow 存在\ y\ 使得\ M_it_i+a_iy=1$

$3.\ 方程组在模\ M\ 意义下的唯一解为：x=\sum\limits_{i=1}^nb_iM_it_i \pmod{M}$

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 11;

int n;
int a[N],b[N];

void exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b) x=1,y=0;
    else 
    {
        exgcd(b,a%b,y,x);
        y-=a/b*x;
    }
}

int main()
{
    cin>>n;

    LL M=1;
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
        M*=a[i];
    }

    LL res=0;
    for(int i=0;i<n;i++)
    {
        LL Mi=M/a[i];
        LL ti,y;
        exgcd(Mi,a[i],ti,y);
        res+=b[i]*Mi*ti;
    }

    cout<<(res%M+M)%M<<endl;

    return 0;
}