- POJ 1006 - Biorhythms
- Time: 1000MS
- Memory: 10000K
- 难度: 初级
- 分类: 中国余数定理
问题描述
详见 http://poj.org/problem?id=1006
这题在 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 四个整数。
已知 (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 = 2、 y = n%5 = 3、 z = 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;
}
