發新話題
打印

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

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

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

TOP

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

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

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

第二串紅字,我的目前所能想到算法是,先求出
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 的餘數

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

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

多喝水。

TOP

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

附件

除以2009的餘數.rar (1.4 KB)

2011-12-11 08:36, 下載次數: 5199

TOP

發新話題