当前位置：首页 > news >正文

POJ 1006（中国剩余定理）

news 来源：原创 2024/4/28 14:17:02

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 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 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.

Hint

Translator

北京大学程序设计实习2007, Xie Di

poj 1006 题的思路不是很难的，可以转化数学式：

现设 num 是下一个相同日子距离开始的天数

p，e，i，d 如题中所设！

那么就可以得到三个式子：( num + d ) % 23 == p； ( num + d ) % 28 == e； ( num + d ) % 33 == i；

p，e，i，d 是我们输入的，那么我们需要求出num即可，为了方便，我们将num+d暂时作为一个整体！令x = num + d；

即：x % 23 == p； x % 28 == e； x % 33 == i；求x

怎么办？这就涉及到所谓的 “ 中国剩余定理 ”( 概念自己google，很easy )

先来看一个故事 “韩信点兵”：
传说西汉大将韩信，由于比较年轻，开始他的部下对他不很佩服。有一次阅兵时，韩信要求士兵分三路纵队，结果末尾多2人，改成五路纵队，结果末尾多3人，再改成七路纵队，结果又余下2人，后来下级军官向他报告共有士兵2395人，韩信立即笑笑说不对（因2395除以3余数是1，不是2），由于已经知道士兵总人数在2300~2400之间，所以韩信根据23，128，233，------，每相邻两数的间隔是105（3、5、7的最小公倍数），便立即说出实际人数应是2333人（因2333=128+20χ105+105，它除以3余2，除以5余3，除以7余2）。这样使下级军官十分敬佩，这就是韩信点兵的故事。

还有就是《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？”答为“23”。

--------这个就是传说中的“中国剩余定理”。其实两个题目的意思就是，n % 3 = 2, n % 5 = 3, n % 7 = 2; 问n是多少？

那么他是怎么解决的呢？

看下面：

题目中涉及 3， 5，7三个互质的数、

令：5 * 7 * a % 3 = 1; --------------> a = 2; 即5 * 7 * 2 = 70；

3 * 7 * b % 5 = 1; --------------> b = 1; 即3 * 7 * 1 = 21；

3 * 5 * c % 7 = 1; --------------> c = 1; 即3 * 5 * 1 = 15；

为什么要使余数为1：是为了要求余数2的话，只要乘以2就可以，要求余数为3的话，只要乘以3就可以！

( 因为题目想要n % 3 =2, n % 5 =3, n % 7 =2; )

那么：要使得n % 3 = 2，那么（ 5 * 7 * 2 ）*2 % 3 = 2；( 因为5 * 7 * 2 % 3 = 1 )

同理：要使得n % 5 = 3，那么（ 3 * 7 * 1 ）*3 % 5 = 3；( 因为3 * 7 * 1 % 5 = 1 )

同理：要使得n % 7 = 2，那么（ 3 * 5 * 1 ）* 2 % 7 = 2；( 因为3 * 5 * 1 % 7 = 1 )

那么现在将（ 5 * 7 * 2 ）* 2和（ 3 * 7 * 1 ）* 3和（ 3 * 5 * 1 ）* 2相加会怎么样呢？我们知道

（ 5 * 7 * 2 ）* 2可以被5和7整除，但是%3等于2

（ 3 * 7 * 1 ）* 3可以被3和7整除，但是%5等于3

（ 3 * 5 * 1 ）* 2可以被3和5整除，但是%7等于2

那么即使相加后，%3， 5， 7的情况也还是一样的！

那么就得到一个我们暂时需要的数（ 5 * 7 * 2 ）* 2 +（ 3 * 7 * 1 ）* 3 +（ 3 * 5 * 1 ）* 2 = 233

但不是最小的!所有我们还要 233 % ( 3 * 5 * 7 ) == 23 得解！

/******************************************************************************************************************************************************/

// 以上就是算法解析，貌似讲的不是很清晰，哎，大家见谅咯~

现在看看此题：x % 23 == p； x % 28 == e； x % 33 == i；求x

按照以上算法：

使 33 * 28 * a % 23 = 1，得a = 6； 33 * 28 * 6 = 5544；

使23 * 33 * b % 28 = 1，得b = 19；23 * 33 * 19 = 14421；
使23 * 28 * c % 33 = 1，得c = 2； 23 * 28 * 2 = 1288。

那么x = 5544 * p + 14421 * e + 1288 * i

那么x-d即相差的时间天数！

因为有范围限制，那么(x-d) %= 21252；且如果此时<=0，那么(x-d) += 21252 ，以上都只是为了保证在范围内而已~

AC代码：

#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    int p, e, i, d, x, y, z, cas = 1;
    x = y = z = 0;
    while(28*33*(++x)%23 != 1) ;
    while(23*33*(++y)%28 != 1) ;
    while(23*28*(++z)%33 != 1) ;
    while(cin >> p >> e >> i >> d)
    {
    	if(p==-1 && e==-1 && i==-1 && d==-1) break;
        p %= 23, e %= 28, i %= 33;
        int ans = (28*33*x*p + 23*33*y*e + 23*28*z*i) %(23*28*33);
        ans = (ans-d) %(23*28*33);
        if(ans <= 0) ans += 23*28*33;
        cout << "Case " << cas++ << ": the next triple peak occurs in "
        << ans << " days." << endl;
    }
    return 0;
}

部分原帖：http://blog.csdn.net/shanshanpt/article/details/8724769