数论-北大-1006

[china_sjc]

源代码：
include<iostream.h>
int main()
{
int a,b,c,d,i=0;
while(cin>>a>>b>>c>>d)
{
i++;
if(a<0)break;
while(a>=23)a-=23;
while(b>=28)b-=28;
while(c>=33)c-=33;
while(a!=b||b!=c||a<=d)
{
if(a<=b&&a<=c){a+=23;continue;}
if(b<=a&&b<=c){b+=28;continue;}
if(c<=a&&c<=b){c+=33;continue;}
}
cout<<"Case "<<i<<": the next triple peak occurs in "<<a-d<<"
days."<<endl;
}
return 0;
}

[china_sjc]

#include <stdio.h>
void main()
{
int p,e,i,d,n;
int num=1;
while(1)
{
scanf("%d%d%d%d",&p,&e,&i,&d);
if(p!=-1)
{
n=(5544*p+14421*e+1288*i-d+21252)%21252;
if(n==0)n=21252;
printf("Case %d: the next triple peak occurs in %d days.\n",num++,n);
}
else break;
}

}

先来看一个故事
传说西汉大将韩信，由于比较年轻，开始他的部下对他不很佩服。有一次阅兵时，韩信要求士兵分三路纵队，结果末尾多2人，改成五路纵队，结果
末尾多3人，再改成七路纵队，结果又余下2人，后来下级军官向他报告共有士兵2395人，韩信立即笑笑说不对（因2395除以3余数是1，不是2），由
于已经知道士兵总人数在2300?/FONT>2400之间，所以韩信根据23，128，233，------，每相邻两数的间隔是105，便立即说出
实际人数应是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 。
是不是一样呢？

呵呵，确实一样。想到这里觉得很兴奋。但是韩信是怎么计算出结果的呢？
随便google了一下，原来这个东西叫“中国剩余定理”，《孙子算经》中就有计算方法。
韩信应该是这样算的：
因为n%3=2,n%5=3,n%7=2且3，5，7互质
使5×7被3除余1，用35×2=70；
使3×7被5除余1，用21×1=21；
使3×5被7除余1，用15×1=15。
（70×2+21×3+15×2）%（3×5×7）=23

同样，这道题也应该是：
使33×28被23除余1，用33×28×8=5544；
使23×33被28除余1，用23×33×19=14421；
使23×28被33除余1，用23×28×2=1288。
（5544×p+14421×e+1288×i）%（23×28×33）=n+d
n=（5544×p+14421×e+1288×i-d）%（23×28×33）
由于我们面对的是计算机，所以以上那些很大的数字，可以单独写程序让电脑在近乎0的时候内求出:) 为什么要单独写呢？嘿嘿，为了主程序
的效率着想～

[china_sjc]

参考资料：http://hi.baidu.com/dinglinbin/blog/item/
c36101d0bae5768da1ec9c54.html

http://hi.baidu.com/myzjdx/blog/item/cba8d460ef4792dc8cb10de9.html

http://www.cppblog.com/AClayton/archive/2007/09/14/32186.aspx

题目分析： 该题本质是“中国同余定理”的变形。
因为只有三个数23 28 33 且三个数两两互为质数，所以“中国剩余定理”可知
对于每一组输入数据p, e ,i, d，所求结果为：n = (R1*p + R2*e + R3*i)%21252-d
其中 R1%p=1, R2%e=1, R3%i=1;
R1 = 5544 = 28*33* 6; //28 33 的公倍数中能被23除余1的最小整数
R2 = 14221 = 23*33*19; //23 33 的公倍数中能被28除余1的最小整数
R3 = 1288 = 23*28* 2; //23 28 的公倍数中能被33除余1的最小整数
为了保证结果大于等于1且小于等于21252，结果修正为：n = (R1*p + R2*e + R3*i - d +
21252)%21252，并且如果n为0，则n = 21252为所求。

程序源码：

//pku1006.cpp
//朱磊 2008-03-28

#include <iostream>
using namespace std;

int main()
{
int p, e, i, d;
int res, n = 1, max = 21252;

while (cin>>p>>e>>i>>d && p != -1) {
res = ((5544*p + 14421*e + 1288*i)%max - d + max)%max;
if (res == 0) {
res = max;
}
cout<<"Case "<<n++<<": the next triple peak occurs in
"<<res<<" days."<<endl;
}
return 0;
}