链接:

https://www.acwing.com/problem/content/206/

题意:

给定2n个整数a1,a2,…,an和m1,m2,mn,求一个最小的非负整数x，满足?i∈[1,n],x≡mi(mod ai)。

思路:

扩展中国剩余定理模板题.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL R[50],M[50];
int n;

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

LL ExCRT()
{
    LL m = M[1],r = R[1],y,gcd;
    for (int i = 2;i <= n;i++)
    {
        gcd = ExGcd(m,M[i],y);
        if ((r-R[i])%gcd != 0)
            return -1;
        x = (r-R[i])/gcd*x%M[i];
        r -= m*x;
        m = m/gcd*M[i];
        r %= m;
    }
    return (r%m+m)%m;
}

int main()
{
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
        scanf("%lld%lld",&M[i],&R[i]);
    printf("%lldn",ExCRT());

    return 0;
}