首页 > 代码库 > POJ_1006_中国剩余
POJ_1006_中国剩余
http://poj.org/problem?id=1006
中国剩余定理用来解求模方程组,用到了逆元。
这题三个数互质,直接用扩展欧几里德可得逆元。
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;int a[5],m[5],n,d;void e_gcd(int a,int b,int &x,int &y){ if(!b) { x = 1; y = 0; return; } e_gcd(b,a%b,x,y); int temp = x; x = y; y = temp-a/b*y;}int CRT(){ int M = 1,ans = 0; for(int i = 1;i <= n;i++) M *= m[i]; for(int i = 1;i <= n;i++) { int x,y,Mi = M/m[i]; e_gcd(Mi,m[i],x,y); ans = (ans+Mi*x*a[i])%M; } if(ans < 0) ans += M; return ans;}int main(){ n = 3; m[1] = 23; m[2] = 28; m[3] = 33; int cnt = 1; while(scanf("%d%d%d%d",&a[1],&a[2],&a[3],&d)) { if(a[1] == -1 && a[2] == -1 && a[3] == -1 && d == -1) break; int ans = CRT(); if(ans <= d) ans += 21252; ans -= d; printf("Case %d: the next triple peak occurs in %d days.\n",cnt++,ans); } return 0;}
POJ_1006_中国剩余
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。