中国剩余定理详解

代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll exgcd(ll a , ll b , ll &x , ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll gcd = exgcd(b , a % b , x , y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return gcd;
}
ll china(ll w[] , ll b[] , ll k)
{
    ll x , y , a = 0 , m , n = 1;
    for(int i = 0 ; i < k ; i++)
        n *= w[i];
    for(int i = 0 ; i < k ; i++)
    {
        m = n / w[i];
        exgcd(w[i] , m , x , y);
        a = (a + y * m * b[i]) % n;
    }
    if(a > 0)
        return a;
    else
        return a + n;
}
int main()
{
    ll a[15] , b[15] , k;
    cin>>k;
    for(int i = 0 ; i < k ; i++)
        cin>>a[i]>>b[i];
    cout<<china(a , b , k) ;
}