孙子定理

题意：
给出一系列线性同余方程：
$x ≡ a[1] (mod m[1])$
$x ≡ a[2] (mod m[2])$
$x ≡ a[3] (mod m[3])$
…
求x的最小值

令$M = m[1] * m[2] * … * m[n]$ ,
令$M[i] = M / m[i]$ , 因为$m[]$中的数两两互质，所以$M[i]$与$m[i]$互质，所以可以用扩欧求出$M[i]$的逆元
$t[i]$是$M[i]$在模$m[i]$下的逆元，即$M[i]*t[i] ≡ 1 (mod\\ m[i])$
$$x = \sum_{i = 1}^{n}{a[i]M[i]t[i]}$$

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 12;

int a[N] , b[N];

void exgcd(LL a , LL b , LL &x , LL &y)
{
    if(!b)
    {
        x = 1 , y = 0;
        return ;
    }

    exgcd(b , a % b , y , x);
    y -= a / b * x;
}

int main()
{
    int n;
    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;
}