POJ 1006 Biorhythms

题目大意:

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

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

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

解题思路:

中国剩余定理,本题的编程并不难,关键在于将题目转化为数学表达式。

提到中国剩余定理,我们首先还是引入一个经典的中国剩余定理的例子。

《孙子算经》中的题目:有物不知其数,三个一数余二,五个一数余三,七个一数又余二,问该物总数几何?

将上面《孙子算经》中的题目转化为数学式:

n = 2(mod3);

n = 3(mod5);

n = 2(mod7);

要求n为多少?

再看看我们这题,转化为数学式子后为:

(n+d) = p(mod23);

(n+d) = e(mod28);

(n+d) = i(mod33);

《孙子算经》中的解法:三三数之,取数七十,与余数二相乘;五五数之,取数二十一,与余数三相乘;七七数之,取数十五,与余数二相乘。将诸乘积相加,然后减去一百零五的倍数。

但是在《孙子算经》中并没有说上面的70、21和15是怎么的出来的。

 下面给出解法:

3*5*a % 7 = 1, 求a。 a=1。得到15;

3*7*a % 5 = 1,  求a。  a=1。得到21;

5*7*a % 3 = 1,  求a。  a=2。得到70.

然后再计算15*2 + 21*3 + 70*2 = 233。

由于3、5、7的最小公倍数为105。所以233 % 105 = 23。

 

用同样的方法可以计算我们这一道题目。

23*28*a % 33 = 1,求a。 a = 2。 得到1288。

23*33*a % 28 = 1,求a。 a = 19。 得到14421。

28*33*a % 23 = 1,求a。 a = 6。 得到5544。

上面a值的计算,可以参考下一篇文章的扩张欧几里得方法。

上面的式子可以转化为w * a = 1 (mod b),如上面的第一个式子,23*28 * a = 1 (mod)28,进一步转换为23*28 * a + 28 * b = 1。就可以扩展欧几里得进行计算了。

23、28、33的最小公倍数为 23*28*33 = 21252。

 

计算得出上面的三个数后,那么 n+d = (1288*i + 14421*e + 5544*p) % (21252)。

那么n = (1288*i + 14421*e + 5544*p - d + 21252) % 21252。

最后的代码也就非常的简单了。

内存:132KB          时间:32MS

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string>
#include <iostream>
#include <stack>
using namespace std;

int main(int argc, const char *argv[])
{
    //freopen("in.txt", "r", stdin);

    int p, e, i, d;
    int caseNum = 0;
    int ans;

    while (true)
    {
        caseNum++;
        scanf("%d %d %d %d", &p, &e, &i, &d);

        if (p == -1 && e == -1 && i == -1 && d == -1)
            break;

        ans = (1288*i + 14421*e + 5544*p - d + 21252) % 21252;
        if (ans == 0)
            ans = 21252;
        printf("Case %d: the next triple peak occurs in %d days.\n", caseNum, ans);
    }

    return 0;
}

  

 

 

原文地址:https://www.cnblogs.com/lovesaber/p/2761112.html