作者  arrenwu (真紅第一騎士)                                      看板  Math 
 標題  Re: [計算] 1!+…+100! 除以 2009 的餘數                                 
 時間  Fri Oct  5 00:13:19 2007                                               
─────────────────────────────────────── 

※ 引述《billyhun (你做了什麼)》之銘言：
: 如題
: 1! + 2! + …… + 100! 除以 2009 的餘數為多少？
: 這題我想很久，試了很多，仍然沒有頭緒，能否給點提示呢？
: 謝謝各位喔^^

1!+2!+3!+..... + 100! = 2009*q + r, 0<= r < 2009

目標是求 r
----
2009 = 7^2*41，

在 41! 之後的數字，都會被 2009 整除。

所以現在要算的是

1!+2!+3!+..... + 40! = 2009*q' + r

分析一下 r 除以 7 的餘數，
可以滿容易地發現等於 1!+2!+3!+.... + 6! mod 7 = 3

可是這樣子 r 的候選人還是太多，
所以加入比較嚴苛的條件，分析 r 除以 49 的餘數，
基本上就是 1!+2!+3!+......+13! mod 49
這部分我是算出 n!(n=1~13) mod 49 的餘數，
分別為 1 2 6 24 22 34 42 42 35 7 28 42 7，
把這些加總除以 49 的餘數是 47，所以現在得到的條件是 r = 49*m+47

然後再使用同樣的手法去分析 r 除以 41 的餘數，
這個比較麻煩，要算 n!(n=1~40) 除以 41 的餘數，
而算出來是發現 r 除以 41 餘 3，也就是 r = 41*n+3。

同時滿足 41*n+3 以及 49*m+47 的 r ，
可以寫成 r = 2009*k + 10827 (那個 10827 是我自己找的)
而這樣的 r ，在 0~2008 之間顯然只有一個。

得出  r = 782 。




--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.192.74.195