首页 > 代码库 > 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 [中国剩余定理]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。