[中譯] ProjectEuler 330 Euler's Number

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (-858993460)時間15年前 (2011/03/27 15:30), 編輯推噓0(009)
留言9則, 1人參與, 最新討論串1/1
330. Euler's Number http://projecteuler.net/index.php?section=problems&id=330 有個實數數列 a(n) 如下定義: / 1 n<0 | a(n) = | ∞ a(n-i) | Σ ------ n≧0 \ i=1 i! 例如, 1 1 1 a(0) = ----- + ----- + ----- + ... = e-1 1! 2! 3! e-1 1 1 a(1) = ----- + ----- + ----- + ... = 2e-3 1! 2! 3! 2e-3 e-1 1 a(2) = ------ + ----- + ----- + ... = (7/2)e-6 1! 2! 3! 其中 e = 2.7182818... 是尤拉常數。 A(n) e + B(n) 可以證明,a(n) 總是滿足如下的形式:---------------, 其中 A(n) 和 B(n) 是整數。 n! 328161643 e - 652694486 例如 a(10) = ------------------------- 10! 求 A(10^9) + B(10^9) 除以 77,777,777 的餘數。 -- いああオレたちには見えてるモノがあるbきっと誰にも奪われないモノがあるはずさ開口一番一虚一実跳梁跋扈形影相弔yL羊頭狗肉東奔西走国士無双南柯之夢 歪も ぶ  意味がないと思えるコトがあるPきっとでも意図はそこに必ずある んの く 依依恋恋空前絶後疾風怒濤有無相生H急転直下物情騷然愚者一得相思相愛 だが ろ 無意味じゃない6あの意図 恋た で 有為転変死生有命蒼天已死黄天當立 !!6五里霧中解散宣言千錯万綜則天去私 のり -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.92

03/28 12:02, , 1F
原來是這樣解的 77777777=7*11*73*101*137
03/28 12:02, 1F

03/28 12:04, , 2F
A(10^9)+B(10^9)分別除以這5個質數的餘數 都有一個循環
03/28 12:04, 2F

03/28 12:04, , 3F
循環的周期剛好是 p*(p-1)
03/28 12:04, 3F

03/28 12:06, , 4F
分別求出對某一個質數的餘數 再總和求出除77777777的餘數
03/28 12:06, 4F

03/28 12:07, , 5F
因為這題是牽涉到ordered bell number,只有O(n^2)的演算法
03/28 12:07, 5F

03/28 12:08, , 6F
剛好求餘的設計選了一個特別的數77777777 可以免去O(n^2)
03/28 12:08, 6F

03/28 12:09, , 7F
慢了一個小時 只拿到21 殘念!
03/28 12:09, 7F

03/28 12:31, , 8F
簡單來說 這題是個陷阱題 數字再大(10^18)還是可以在1分鐘
03/28 12:31, 8F

03/28 12:32, , 9F
內跑完...這種陷阱,倒是很符合謎題的特質
03/28 12:32, 9F
文章代碼(AID): #1DZkUU4c (puzzle)
文章代碼(AID): #1DZkUU4c (puzzle)