100!的結尾 - 拼圖

: 推 stimim: 心算好像也不是不行，很勉強就是了，先把 5 和 2 算完 12/26 19:43
: → stimim: 奇數的部份只考慮尾數 1 3 7 9 ，一組乘起來還是 9 12/26 19:44
: → stimim: 偶數的部份除一次 2 會有一半變奇數，就用奇數的方法解 12/26 19:47
: → stimim: 剩下的偶數再除 2 又有一半變奇數，直到只剩一個數為止 12/26 19:48
是說, 如果只是要快速紙筆算的話, 用↑這些東西其實就足夠了:

在紙上寫出所要求的 n, 然後在旁邊和下面寫成一張表; 以 100 為例會寫成這樣:

100 50 25 12 6 3 1

20 10 5 2 1

4 2 1

寫表的規則是往右除以 2 向下取整, 往下除以 5 向下取整, 寫到 0 為止

接下來的動作是:

(A) 把這些數十位以上的部份每 20 消掉, 如果有剩下 10 則記下兩個「3」

這裡 100 和 20 自己消掉, 50 消掉兩個 20 剩下的 10 和它下面的 10 對消

25 的 20 消掉, 剩下 12 的 10

(B) 個位數把 1 2 7 8 劃掉, 3 4 5 6 合起來數個數當做「3」, 9 算兩個「3」

累積四個則可以一起消掉

這裡劃掉後合計一共五個「3」, 去掉四個剩下一個

(C) 求出 (A)(B) 總共多少個「3」, 求 3 的這麼多次方的個位數

這裡總計三個「3」所以個位是 3^3 = 27 → 7

這部份是在計算扣掉 2 和 5 的因數之後剩下的部份乘積的個位數

表中的數字表示我們需要考慮 1 到此數之間所有個位是 1 3 7 9 的數乘起來

偶數部份把所有數拿掉一個 2 後即是由表中它右邊的數負責

五的倍數部份也是同理, 由表中它下面的數負責

所以到最後表中每一格都負責了一部份數 (2 和 5 有特定個數的數會給同一格負責)

然後對每一格求乘積, 利用兩組 1 3 7 9 乘起來個位是 1 消掉 20

一組 1 3 7 9 乘起來個位是 9 = 3*3, 個位剩 9 也是這邊

然後個位餘數, 1 2 的乘積只有 1, 3 4 5 6 是 1*3 = 3, 7 8 是 1*3*7 = 21

所以劃掉 1 2 7 8, 收集 3 4 5 6 每個為乘積個位貢獻一個 3

接著就求 3 的這麼多次方的個位即可, 週期是 3-9-7-1 所以每四個「3」也可以消掉

(D) 再來要求表最上列的和減去表最左行的和, 當然最左上自己消掉所以不管

剩下的最左行的和會很接近最上列左數第三個數 (n/4), 和它消掉

最上列其餘的數總計時把 4 的倍數也消掉

最後剩下的總和就求 2 的次方的個位數

這裡最左行總和是 24, 和 25 消掉剩 1

50 餘 2, 12 倍數, 6 餘 2 和 50 消, 3 和 25 剩下的 1 消, 剩下 1, 2^1 = 2

很容易發現這裡就是在算乘積中 2 的次方有多少

剩下的最左行的和會接近 n/4 的理由是 (1/5)/(1-1/5) = 1/4

差距通常會只有 1~2, 不過還是要算一下避免出事

(這裡可以只用個位求和來求差距, 因為結果總是不大且減完一定有剩)

然後總計時消掉 4 的倍數同樣是利用 2 的次方個位週期 2-4-8-6

這裡要稍微注意的是如果消光了那這裡應該要押 2^4 = 16 的 6 不是 2^0 = 1

(E) (C)*(D) 的個位即是最終答案了: 7*2 = 14 → 4 得 100! 末位非零是 4

這樣寫了很大一篇但實際操作起來就是劃掉劃掉再劃掉

最後剩下的結果就能馬上心算求得答案

我自己實驗過用這樣的劃法算 1000! 的末位非零大概一分鐘左右就有答案 [答案是 2]

應該算是個不錯的紙筆速算法

--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513

--