poj1006——生理周期

中国同余定理的应用。

看一个例子 你就明白：

例 1 ：一个数被 3 除余 1 ，被 4 除余 2 ，被 5 除余 4 ，这个数最小是几？
题中 3 、 4 、 5 三个数两两互质。
则〔 4 ， 5 〕 =20 ；〔 3 ， 5 〕 =15 ；〔 3 ， 4 〕 =12 ；〔 3 ， 4 ， 5 〕 =60 。
为了使 20 被 3 除余 1 ，用 20×2=40 ；
使 15 被 4 除余 1 ，用 15×3=45 ；
使 12 被 5 除余 1 ，用 12×3=36 。
然后， 40×1 ＋ 45×2 ＋ 36×4=274 ，
因为， 274>60 ，所以， 274 － 60×4=34 ，就是所求的数。 来源于：http://eblog.cersp.com/userlog/7978/archives/2008/723693.shtml

将此算法应用于此题即可！该注意的一点问题已在程序中标注。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 21252
int main()
{
	int p,e,i,d,ca=1;
	while(1)
	{
		cin>>p>>e>>i>>d;
		if(p+e+i+d==-4) break;
		const int r1=23,r2=28,r3=33;
		int re1=r2*r3,re2=r1*r3,re3=r1*r2,re=r1*r2*r3;
		int res1=re1,res2=re2,res3=re3;
		while(res1%r1!=1) res1+=re1;
		while(res2%r2!=1) res2+=re2;
		while(res3%r3!=1) res3+=re3;	
		res1*=p;res2*=e;res3*=i;
		int k=re;
		while(res1+res2+res3>k)
		{
			k+=re;
		}
		k-=re;
		int t=(res1+res2+res3-k-d+21252)%21252;//可能出现负数  故加之后再取余！
		if(t==0)
			printf("Case %d: the next triple peak occurs in %d days.\n",ca++,21252);
		else printf("Case %d: the next triple peak occurs in %d days.\n",ca++,t);
	}
	return 0;
}