首页 > 代码库 > poj 2891 Strange Way to Express Integers
poj 2891 Strange Way to Express Integers
http://poj.org/problem?id=2891
这道题的题意是:给你多个模性方程组:m mod ai=ri 求最小的m;
中国剩余定理
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll long long 5 using namespace std; 6 7 ll gcd(ll a,ll b,ll &x,ll &y) 8 { 9 if(!b) 10 { 11 x=1; 12 y=0; 13 return a; 14 } 15 ll d=gcd(b,a%b,y,x); 16 y-=x*(a/b); 17 return d; 18 } 19 20 int main() 21 { 22 ll a1,t,r1,x,y,a2,r2; 23 while(scanf("%lld",&t)!=EOF) 24 { 25 scanf("%lld%lld",&a1,&r1); 26 t--; 27 bool flag=true; 28 while(t--) 29 { 30 scanf("%lld%lld",&a2,&r2); 31 if(!flag) continue; 32 ll d1=gcd(a1,a2,x,y); 33 ll c=r2-r1; 34 if(c%d1) 35 { 36 flag=false; 37 continue; 38 } 39 ll t1=a2/d1; 40 x=(c/d1*x%t1+t1)%t1; 41 r1=(a1*x+r1); 42 a1=a1*a2/d1; 43 } 44 if(!flag) printf("-1\n"); 45 else printf("%lld\n",r1); 46 } 47 return 0; 48 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。