久久久久免费,欧美福利网址,免费一区二区三区

PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的

http://acm.pku.edu.cn/JudgeOnline/problem?id=1006
            題目名字叫Biorhythms，翻譯過來大概是“生物節律”吧。
            這道題并不難，但是，挺有意思的。
            先來看一個故事
      傳說西漢大將韓信，由于比較年輕，開始他的部下對他不很佩服。有一次閱兵時，韓信要求士兵分三路縱隊，結果末尾多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的時候內求出:) 為什么要單獨寫呢？嘿嘿，為了主程序的效率著想～

    程序已經出來了

#include <stdio.h>
2

void main()
3

{
4

int p,e,i,d,n;
5

int num=1;
6

while(1)
7

{
8

scanf("%d%d%d%d",&p,&e,&i,&d);
9

if(p!=-1)
10

{
11

n=(5544*p+14421*e+1288*i-d+21252)%21252;
12

if(n==0)n=21252;
13

printf("Case %d: the next triple peak occurs in %d days.\n",num++,n);
14

}
15

else break;
16

}
17

}

呵呵，事情到此為止我已經十分開心了，因為我看到還有很多用各種各樣方法搞得頭昏腦脹都還沒有ac的同學們。大家加油吧～
但是，還有一點想不明白，我的Memory用了72K，查看這道題的status，很多人竟然只用了20K內存就做出來了，最強的竟然只用了4K！難道有更好的算法？？百思不得其解。。。如果有人知道，請告訴我，感謝。

posted on 2007-09-14 02:12 流牛ζ木馬閱讀(3927) 評論(10) 編輯收藏引用

使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）

第一行應該是：使33×28被23除余1，用33×28×6=5544；回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的 2008-12-03 20:49 days

sum = (5544*p +14421*e + 1288*i)%21252;
days = sum -d;
請教一下這樣那里出了問題
一直wa 回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的 2008-12-03 20:56 days

（5544×p+14421×e+1288×i）%（23×28×33）=n+d

如果
sum ＝ n+d
n = sum -d
? 回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的 2009-01-15 22:54 畫中的黑馬

終于看懂了！
“ 同樣，這道題也應該是：
使33×28被23除余1，用33×28×8=5544；
使23×33被28除余1，用23×33×19=14421；
使23×28被33除余1，用23×28×2=1288。 ”
這一段好難看明白哦回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的[未登錄] 2009-05-02 16:50 菜鳥

6,19,2是怎么得到的啊回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的[未登錄] 2009-05-02 17:05 菜鳥

看懂了……報告中的錯誤也太“低級”了，苦了菜鳥我啊
回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的 2011-08-03 21:53 Tinylamb

@days
沒問題。因為(a+b)%c=（a%c+b%c）%c 回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的[未登錄] 2011-10-05 00:08 huhu

為什么是*8，*19，*2，百度上看的不是很懂，希望樓主賜教~~拜托了！！！回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的 2012-06-18 10:40 wpj112

使5×7被3除余1，用35×2=70；
上句中 5*7被3除是余2呀，筆誤呀，作者？回復更多評論

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的 2016-03-09 16:17 physhy

@wpj112
看好，是使它的結果為1。那么你就要湊出5*7*n%3=1，n最小為2。回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2007年9月

日

一

二

三

四

五

六

統計

隨筆 - 63
文章 - 0
評論 - 154
引用 - 0

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木馬

常用鏈接

留言簿(6)

隨筆檔案

相冊

撒旦

搜索

閱讀排行榜

評論排行榜

# re: PKU POJ 1006 Biorhythms 從“韓信點兵”中想到的 2008-08-07 17:52 lihongbo1008@163.com