中国剩余定理模数不互质的情况（poj 2891

中国剩余定理模数不互质的情况
主要有一个ax+by==k*gcd(a,b),注意一下倍数情况和最小

https://vjudge.net/problem/POJ-2891

#include <iostream>

#include <cstdio>

#include <queue>

#include <algorithm>

#include <cmath>

#include <cstring>

#define inf 2147483647

#define N 1000010

#define p(a) putchar(a)

#define For(i,a,b) for(long long i=a;i<=b;++i)

//by war

//2019.8.8

using namespace std;

long long T,n;

long long r[N],a[N],x,y,gcd,flag;

void in(long long &x){

    long long y=;char c=getchar();x=;

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c<=''&&c>=''){ x=(x<<)+(x<<)+c-'';c=getchar();}

    x*=y;

}

void o(long long x){

    if(x<){p('-');x=-x;}

    if(x>)o(x/);

    p(x%+'');

}

void exgcd(long long a,long long b,long long &x,long long &y){

    if(!b){

        x=;y=;gcd=a;

        return;

    }

    exgcd(b,a%b,y,x);

    y-=a/b*x;

}

signed main(){

    while(scanf("%lld",&n)!=EOF){

        flag=;

        For(i,,n)

           in(r[i]),in(a[i]);

        For(i,,n){

            exgcd(r[],r[i],x,y);

            if((a[i]-a[])%gcd==){

                x*=(a[i]-a[])/gcd;

                y=r[i]/gcd;

                x=(x%y+y)%y;

                a[]+=r[]*x;

                r[]=r[]*r[i]/gcd;

            }

            else{

                o(-);p('\n');

                flag=;

                break;

            }

        }

        if(!flag)

            o(a[]%r[1]),p('\n');

    }

    return ;

}