作者LPH66 (-858993460)
看板puzzle
标题[中译] ProjectEuler 330 Euler's Number
时间Sun Mar 27 15:30:36 2011
330. Euler's Number
http://projecteuler.net/index.php?section=problems&id=330
有个实数数列 a(n) 如下定义：
/ １ n＜0
|
a(n) = | ∞ a(n-i)
| Σ ------ n≧0
\ i=1 i!
例如，
1 1 1
a(0) = ----- + ----- + ----- + ... = e-1
１! ２! ３!
e-1 1 1
a(1) = ----- + ----- + ----- + ... = 2e-3
１! ２! ３!
2e-3 e-1 1
a(2) = ------ + ----- + ----- + ... = (7/2)e-6
１! ２! ３!
其中 e = 2.7182818... 是尤拉常数。
A(n) e + B(n)
可以证明，a(n) 总是满足如下的形式：---------------, 其中 A(n) 和 B(n) 是整数。
ｎ!
328161643 e - 652694486
例如 a(10) = -------------------------
10!
求 A(10^9) + B(10^9) 除以 77,777,777 的余数。
--
い
ああオレたちには见えてるモノがあるbデ きっと谁にも夺われないモノがあるはずさ
け
开口一番一虚一実跳梁跋扈形影相吊yュL羊头狗肉东奔西走国士无双南柯之梦 歪も
ぶ
意味がないと思えるコトがある ラPきっとでも意図はそこに必ずある んの
く
依依恋恋空前絶後疾风怒涛有无相生 ラH急転直下物情骚然愚者一得相思相爱 だが
ろ
无意味じゃない ラ6あの意図が 恋た
で
有为転変死生有命苍天已死黄天当立 !!6五里雾中解散宣言千错万综则天去私 のり
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.28.92
1F：→ utomaya:原来是这样解的 77777777=7*11*73*101*137 03/28 12:02
2F：→ utomaya:A(10^9)+B(10^9)分别除以这5个质数的余数 都有一个循环 03/28 12:04
3F：→ utomaya:循环的周期刚好是 p*(p-1) 03/28 12:04
4F：→ utomaya:分别求出对某一个质数的余数 再总和求出除77777777的余数 03/28 12:06
5F：→ utomaya:因为这题是牵涉到ordered bell number,只有O(n^2)的演算法 03/28 12:07
6F：→ utomaya:刚好求余的设计选了一个特别的数77777777 可以免去O(n^2) 03/28 12:08
7F：→ utomaya:慢了一个小时 只拿到21 残念! 03/28 12:09
8F：→ utomaya:简单来说 这题是个陷阱题 数字再大(10^18)还是可以在1分钟 03/28 12:31
9F：→ utomaya:内跑完...这种陷阱，倒是很符合谜题的特质 03/28 12:32