19——poj 1006中国剩余定理


先来看一个故事 “韩信点兵”:
      传说西汉大将韩信,由于比较年轻,开始他的部下对他不很佩服。有一次阅兵时,韩信要求士兵分三路纵队,结果末尾多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 且 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

此题同解

http://poj.org/problem?id=1006

#include <iostream>
#include <cstdio>
using namespace std;
#define N 21252
int main()
{
int p,e,i,d,x;
int k=1;
while(cin>>p>>e>>i>>d)
{
if(p==-1&&e==-1&&i==-1&&d==-1)
break;
int a,b,c;
for(int j=28*33+1;;j++)
{
if(j%(28*23)==0&&j%33==1)
{
a=j;
break;
}
}
for(int j=33*23+1;;j++)
{
if(j%(33*23)==0&&j%28==1)
{
b=j;
break;
}
}
for(int j=33*28+1;;j++)
{
if(j%(28*33)==0&&j%23==1)
{
c=j;
break;
}
}
x=(a*i+b*e+c*p)%(23*28*33)-d;
if(x<=0)
x+=N;
printf("Case %d: the next triple peak occurs in %d days.\n",k++,x);
}
return 0;
}



评论

© 现实给了梦想多少时间 | Powered by LOFTER