[中譯] ProjectEuler 330 Euler's Number

[LPH66 (-858993460)]

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
→ utomaya:原來是這樣解的 77777777=7*11*73*101*137
→ utomaya:A(10^9)+B(10^9)分別除以這5個質數的餘數 都有一個循環
→ utomaya:循環的周期剛好是 p*(p-1)
→ utomaya:分別求出對某一個質數的餘數 再總和求出除77777777的餘數
→ utomaya:因為這題是牽涉到ordered bell number,只有O(n^2)的演算法
→ utomaya:剛好求餘的設計選了一個特別的數77777777 可以免去O(n^2)
→ utomaya:慢了一個小時 只拿到21 殘念!
→ utomaya:簡單來說 這題是個陷阱題 數字再大(10^18)還是可以在1分鐘
→ utomaya:內跑完...這種陷阱，倒是很符合謎題的特質