首页 > 代码库 > POJ Strange Way to Express Integers [中国剩余定理]

POJ 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\n",a1);    }}

 

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