扩展中国剩余定理

poj2891

//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
#define LL long long
const int maxn=100000+5;
LL n,RES[maxn],M[maxn];
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
template<class T> void exgcd(T a,T b,T &d,T &x,T &y){
    if(!b) {d=a;x=1;y=0;}
    else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
template<class T> T mod_reverse(T a,T n){
    T x,y,d;
    exgcd(a,n,d,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
LL EX_CRT(){
    bool flag=true;
    for(int i=1;i<n;i++){
        LL M1=M[i-1],M2=M[i],RES1=RES[i-1],RES2=RES[i],T=gcd(M1,M2);
        if((RES2-RES1)%T) {
            flag=false;
            break;
        }
        M[i]=(M1*M2)/T;
        RES[i]=(mod_reverse(M1/T,M2/T)*(RES2-RES1)/T)%(M2/T)*M1+RES1;
        RES[i]=(RES[i]%M[i]+M[i])%M[i];
    }
    return flag?RES[n-1]:-1;

}

int main(){
    while(scanf("%I64d",&n)==1){
        for(int i=0;i<n;i++)
            scanf("%I64d%I64d",&M[i],&RES[i]);
        printf("%I64d
",EX_CRT());
    }
}