POJ2891 Strange Way to Express Integers [中国剩余定理]

不互质情况的模板题

注意多组数据不要一发现不合法就退出

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
ll n,a1,m1,a2,m2;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(b==0) d=a,x=1,y=0;
    else exgcd(b,a%b,d,y,x),y-=(a/b)*x;
}
int main(){
    freopen("in","r",stdin);
    while(scanf("%lld",&n)!=EOF){
        int flag=0;
        m1=read();a1=read();n--;
        while(n--){
            m2=read();a2=read();
            if(flag) continue;
            ll d,t1,t2;
            exgcd(m1,m2,d,t1,t2);
            if((a2-a1)%d){flag=1;continue;}
            t1*=(a2-a1)/d;
            m2/=d;
            t1=(t1%m2+m2)%m2;
            a1=a1+m1*t1;
            m1*=m2;
        }
        if(flag) puts("-1");
        else printf("%lld
",a1);
    }
}