首页 > 代码库 > POJ 1006
POJ 1006
直接使用中国剩余定理
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int r=3;int m[4]={0,23,28,33};int a[4]={0};void exgcd(int a,int b,int &d,int &x,int &y){ if(b==0){ x=1; y=0; d=a; } else{ exgcd(b,a%b,d,x,y); int tmp=x; x=y; y=tmp-(a/b)*y; }}int China(int lim){ int M=1; int i,Mi,x,y,d,ans=0; for(i=1;i<=r;i++) M*=m[i]; for(i=1;i<=r;i++){ Mi=M/m[i]; exgcd(Mi,m[i],d,x,y); ans=(ans+Mi*x*a[i])%M; } while(ans<=lim) ans+=M; return ans;}int main(){ int d,p,e,i; int kase=0; while(scanf("%d%d%d%d",&p,&e,&i,&d)!=EOF){ if(p==-1&&d==-1&&e==-1&&i==-1) break; a[1]=p; a[2]=e; a[3]=i; int ans=China(d); printf("Case %d: the next triple peak occurs in %d days.\n",++kase,ans-d); } return 0;}
POJ 1006
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。