首页 > 代码库 > poj 1006(剩余定理)

poj 1006(剩余定理)

生理周期
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 111426 Accepted: 34702

Description

人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如,智力周期的高峰,人会思维敏捷,精力容易高度集中。因为三个周期的周长不同,所以通常三个周期的高峰不会落在同一天。对于每个人,我们想知道何时三个高峰落在同一天。对于每个周期,我们会给出从当前年份的第一天开始,到出现高峰的天数(不一定是第一次高峰出现的时间)。你的任务是给定一个从当年第一天开始数的天数,输出从给定时间开始(不包括给定时间)下一次三个高峰落在同一天的时间(距给定时间的天数)。例如:给定时间为10,下次出现三个高峰同天的时间是12,则输出2(注意这里不是3)。

Input

输入四个整数:p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间(时间从当年的第一天开始计算)。d 是给定的时间,可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252。 

当p = e = i = d = -1时,输入数据结束。

Output

从给定时间起,下一次三个高峰同天的时间(距离给定时间的天数)。 

采用以下格式: 
Case 1: the next triple peak occurs in 1234 days. 

注意:即使结果是1天,也使用复数形式“days”。

Sample Input

0 0 0 00 0 0 1005 20 34 3254 5 6 7283 102 23 320203 301 203 40-1 -1 -1 -1

Sample Output

Case 1: the next triple peak occurs in 21252 days.Case 2: the next triple peak occurs in 21152 days.Case 3: the next triple peak occurs in 19575 days.Case 4: the next triple peak occurs in 16994 days.Case 5: the next triple peak occurs in 8910 days.Case 6: the next triple peak occurs in 10789 days.


一开始自己做这道题时,样例全可以过,可就是AC不了。
从http://www.cnblogs.com/walker01/archive/2010/01/23/1654880.html处摘抄的剩余定理的有关资料,他讲的很明白,很详细。
中国剩余定理介绍

     在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二(除以3余2),五五数之剩三(除以5余3),七七数之剩二(除以7余2),问物几何?”这个问题称为“孙子问题”,该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步:

  1. 找出三个数:从3和5的公倍数中找出被7除余1的最小数15,从3和7的公倍数中找出被5除余1 的最小数21,最后从5和7的公倍数中找出除3余1的最小数70。
  2. 用15乘以2(2为最终结果除以7的余数),用21乘以3(3为最终结果除以5的余数),同理,用70乘以2(2为最终结果除以3的余数),然后把三个乘积相加(15*2+21*3+70*2)得到和233。
  3. 用233除以3,5,7三个数的最小公倍数105,得到余数23,即233%105=23。这个余数23就是符合条件的最小数。

 

     根据剩余定理:

                       1.(23*28*i)%33=1;  i=2;   23*28*2=1288;

                       2.(23*33*j)%28=1;  j=19;   23*33*19=14421;

                       3.(28*33*k)%23=1;  k=6;  28*33*6=5544;

由此就可以得出:5544*p+14421*e+1288*i ;再根据题意做适当的调整。

 

#include <stdio.h>int main(){    int  p, e, i, d;    int num = 0;    int days;    while(scanf("%d%d%d%d", &p, &e, &i, &d) != EOF)    {        if(p==-1 &&e==-1 &&i==-1 &&d==-1)            break ;            days=(5544*p+14421*e+1288*i-d+21252)%21252;  //后面加21252是防止它变成负数            if(days ==0)                days=21252;            printf("Case %d: the next triple peak occurs in %d days.\n", ++num,days);    }    return 0;}