Math Pro 數學補給站's Archiver

時間就像一張網,
你撒在哪裡,
你的收獲就在那裡。

M9331707 發表於 2007-10-29 09:55

整數論題目,1!+2!+3!+..... + 100! 除以 2009,求餘數 r

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

weiye 發表於 2007-11-5 16:16

我目前所能想到的方法跟你在全教會論壇提供的那篇一樣,

[url=http://forum.nta.org.tw/examservice/showthread.php?t=35235]http://forum.nta.org.tw/examservice/showthread.php?t=35235[/url]

第一串紅字,我想應該是直接算。

第二串紅字,我的目前所能想到算法是,先求出
mod 41  的每個元素的乘法反元素,
如下(都是利用輾轉相除法找出)

1×1≡1 mod 41
2×21≡1 mod 41
3×14≡1 mod 41
4×31≡1 mod 41
5×33≡1 mod 41
6×7≡1 mod 41
8×36≡1 mod 41
9×32≡1 mod 41
10×37≡1 mod 41
11×15≡1 mod 41
12×24≡1 mod 41
13×19≡1 mod 41
16×18≡1 mod 41
17×29≡1 mod 41
20×39≡1 mod 41
22×28≡1 mod 41
23×25≡1 mod 41
26×30≡1 mod 41
27×38≡1 mod 41
34×35≡1 mod 41
40×40≡1 mod 41

除了 1 跟 40 的乘法反元素為本身之外,其他的乘法反元素皆不為本身。

用這 21 個式子輔助求算 n!(n=1~40) 除以 41 的餘數

這樣還是很不方便,目前還沒有想到更快的方法,

等待高手指點更好的方法囉。 :-)

bugmens 發表於 2011-12-11 08:36

這是2007年PTT的一篇文章,無論如何一定要計算除以41的餘數,所以文章只是當做紀念而已

頁: [1]

論壇程式使用 Discuz! Archiver 6.1.0  © 2001-2007 Comsenz Inc.