首页 > 代码库 > 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