阿九大战朱最学

这个题目可能就是带了描述的中国剩余定理了吧?
是不是越学越***？

//ex_gcd解ax+by=gcd(a,b).其中a,b必须互质,显然当x=1,y=0是一组解.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=15;
ll a[N],b[N],m[N],t[N];
ll x,y;
void ex_gcd(ll aa,ll bb)
{
    if(bb==0)
    {
        x=1,y=0;
        return;
    }
    ex_gcd(bb,aa%bb);
    ll cx=x;ll cy=y;
    x=cy; y=(cx-aa/bb*cy);
}

int main()
{
    ll n,M=1;
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        M=a[i]*M;
    }
    for(ll i=1;i<=n;i++)
    {
        m[i]=M/a[i];
    }
    for(ll i=1;i<=n;i++)
    {
        ex_gcd(m[i],a[i]);
        t[i]=x;
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        ans=(ans+b[i]*m[i]%M*t[i])%M;
    }
    cout<<(ans+M)%M<<endl;
    return 0;
}