POJ 1006 - Biorhythms


问题描述

这题在POJ上有译文(原文右上角)。

解题思路

中国剩余定理,本题难点不在编程,而是分析题目并转化为数学公式

要引入本题解法,先来看一个故事 “韩信点兵”:

传说西汉大将韩信,由于比较年轻,开始他的部下对他不很佩服。有一次阅兵时,韩信要求士兵分三路纵队,结果末尾多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)。这样使下级军官十分敬佩,这就是韩信点兵的故事。


韩信点兵问题简化:已知 n%3=2, n%5=3, n%7=2, 求n

再看我们这道题,读入p,e,i,d 4个整数

已知 (n+d)%23=p; (n+d)%28=e; (n+d)%33=i ,求n 。

两道题是一样的。但是韩信当时是如何计算出结果的?

韩信用的就是“中国剩余定理”,《孙子算经》中早有计算方法,大家可以查阅相关资料。

“韩信点兵”问题计算如下:

因为 n%3=2, n%5=3, n%7=2 且 3,5,7互质 (互质可以直接得到这三个数的最小公倍数)

x= n%3=2y= n%5=3z= n%7=2

  • 使 5×7×a 被3除余1,有 35×2=70,即 a=2
  • 使 3×7×b 被5除余1,用 21×1=21,即 b=1
  • 使 3×5×c 被7除余1,用 15×1=15,即 c=1
  • 那么 n =(70×x+21×y+15×z)%lcm(3,5,7) = 23 这是n的最小解

而韩信已知士兵人数在 2300~2400 之间,所以只需要 n+i×lcm(3,5,7) 就得到了2333,此时 i=22


同样,这道题的解法就是:

已知 (n+d)%23=p; (n+d)%28=e; (n+d)%33=i

  • 使 33×28×a 被23除余1,用 33×28×8=5544
  • 使 23×33×b 被28除余1,用 23×33×19=14421
  • 使 23×28×c 被33除余1,用 23×28×2=1288
  • 因此有 (5544×p+14421×e+1288×i)% lcm(23,28,33) = n+d

又23、28、33互质,即 lcm(23,28,33) = 21252;

所以有 n =(5544×p+14421×e+1288×i-d)% 21252


本题所求的是最小整数解,避免n为负,因此最后结果为 n= [n+21252] % 21252

那么最终求解n的表达式就是:n=(5544*p+14421*e+1288*i-d+21252)%21252

当问题被转化为一条数学式子时,你会发现它无比简单。。。。直接输出结果了。

AC 源码

//Memory Time 
//256K   94MS 

#include<iostream>
using namespace std;

int main(void)
{
    int p,e,i,d;
    int time=1;
    while(cin>>p>>e>>i>>d)
    {
        if(p==-1 && e==-1 && i==-1 && d==-1)
            break;

        int lcm=21252;  // lcm(23,28,33)
        int n=(5544*p+14421*e+1288*i-d+21252)%21252;
        if(n==0)
            n=21252;
        cout<<"Case "<<time++<<": the next triple peak occurs in "<<n<<" days."<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1905 - Expanding Rods POJ 1905 - Expanding Rods
POJ 1905 - Expanding Rods Time: 1000MS Memory: 30000K 难度: 初级 分类: 二分法 问题描述一根两端固定在两面墙上的杆 受热弯曲后变弯曲 求前后两个状态的杆的中点位置的距离 解题思路
2011-07-16
下一篇 
POJ 3020 - Antenna Placement POJ 3020 - Antenna Placement
POJ 3020 - Antenna Placement Time: 1000MS Memory: 65536K 难度: 初级 分类: 二分图 问题描述一个矩形中,有N个城市 *,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可
2011-07-09
  目录