中国剩余定理

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n,u[105],v[105],lcm;

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

ll china1() /// 互质
{
    ll res=0, x, y;
    for(int i=1;i<=n;i++) lcm=lcm*u[i];
    for(int i=1;i<=n;i++) {
        ll t=lcm/u[i];
        ll gcd=exgcd(t,u[i],x,y);
        x=(x%u[i]+u[i])%u[i];
        res=(res+v[i]*x*t)%lcm;
    }
    return res;
}
ll china2() /// 不互质
{
    ll U=u[1], V=v[1], x, y, gcd;
    for(int i=2;i<=n;i++) {
        exgcd(U,u[i],gcd,x,y);
        if((v[i]-V)%gcd) return -1; 
        ll t=u[i]/gcd; x=(x*(v[i]-V)/gcd%t+t)%t;
        V+=U*x, U=U/gcd*u[i], V%=U;
    }
    V=(V%U+U)%U;
    if(n==1 && V==0) return U;
    return V;
}

int main()
{
    while(~scanf("%lld",&n)) {
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",&u[i],&v[i]);
        lcm=1; printf("%lld %lld
",china1(),china2());
    }

    return 0;
}