之前整理的有点问题,一直没判断不存在的情况,可以确定的是当m不互素的时候是有没有接的情况,题解在下面,具体原理有时间可以搜一下题解,现在就当成线性方程组解的。

!如果互素的话,一定有没有解需要考虑下,在这埋个坑!

#include<iostream>
#define LL long long
using namespace std;
LL exgcd(LL a,LL b, LL &x,LL &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    LL q=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return q;
}
LL CRT(LL m[],LL r[],LL n){
    LL M = m[0], R = r[0], x, y, d;
    for (int i = 1; i < n; ++i)
    {
        d = exgcd(M, m[i], x, y);
        if ((r[i] - R) % d) 
            return -1;
        x = (r[i] - R) / d * x % (m[i] / d);
        R += x * M;
        M = M / d * m[i];
        R %= M;
    }
    return R > 0 ? R : R + M;
}
int main(){
    LL a[50000],m[50000];
    LL n;
    while(cin>>n){
        for(int i = 0; i < n; i++){
            cin >> a[i] >> m[i];
        }
    cout<<CRT(a,m,n)<<endl;    
    }
    //system("pause");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注