首页 > 代码库 > poj 1006（剩余定理）

poj 1006（剩余定理）

2024-07-09 23:33:11   219人阅读

生理周期
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;}

 

 


联系
我们