100!的結尾 - 拼圖

※ 引述《ACGfans (ACGfans)》之銘言：
: 100! 是一個很大的數字
: 其結尾帶有許多 0
: 問題: 從尾巴數過來，第一個不是 0 的數字為何?

參考答案： (公式推導)

=== 1 ===
令 A = n! = 2^a_2 * 3^a_3 * 5^a_5 * 7^a_7 * 11^a_11 * ...

Q = A / (10^a_5)

則所求 = Q mod 10

而且對所有 n > 1 都有 a_2 > a_5

所以 Q mod 2 == 0

如果我們知道 (Q mod 5) 就可以求出 Q mod 10

=== 2 ===
令 X = A / 5^a_5 ==> Q = X / 2^a_5

Q mod 5 = X * 3^a_5 mod 5 (因為 3 和 2 mod 5 時互為倒數)

=== 3 ===
求 X mod 5

X 是 n! 把所有的 5 除掉

我們把 1 ~ n 分成 5 個 5 個一組

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
...

先不管 5 的倍數，我們先把其他的數 mod 5

1 2 3 4 5
1 2 3 4 10
1 2 3 4 15
...

X = (4!)^[n/5] * (n mod 5)! * (5 的倍數的共獻)
( [n/5] 是 n/5 取下高斯 )
( 4! mod 5 = 4 )
( (n mod 5)! 是最後沒組滿 1~4 的那一組 )

記算 "5 的倍數的共獻" 時，我們可以把每個數都先除 5

數字就變成 1 2 3 ... [n/5] ，所以又變成一樣的問題，
把 [n/5] 當成 n 代回去

X = 4^[n / 5] * (n mod 5)! * 4^[n / 5^2] * ([n / 5] mod 5)! * ...

=== 4 ===
解化剛剛的結果：

3 的結果中，我們用到了
[n / 5], n mod 5,
[n / 5^2], [n / 5] mod 5,
[n / 5^3], [n / 5^2] mod 5

[n / 5^k] mod 5 其實就是把 n 用 5 進位表示時的第 k 位數

n = b_0 + b_1 * 5 + b_2 * 5^2 + ...

b_k = [n / 5^k] mod 5

X = 4^[n / 5] * b_0! * 4^[n / 5^2] * b_1! * 4^[n / 5^3] * b_2! + ...

[n / 5^k] = b_k + b_{k+1} * 5^1 + b_{k+2} * 5^2 + ...

另外， 4^m mod 5 = 4^(m mod 4) mod 5 因為 4^4 mod 5 == 1

4^[n / 5^k] mod 5 = 4^(b_k + b_{k+1} * 5^1 + b_{k+2} * 5^2 + ...) mod 5
= 4^(b_k + b_{k+1} * 5^1 + b_{k+2} * 5^2 + ... mod 4) mod 5

因為 5 mod 4 == 1

4^[n / 5^k] mod 5 = 4^(b_k + b_{k+1} + b_{k+2} + ...) mod 5
(太神啦，5^k 都不見了)

X = b_0! *
4^(b_1 + b_2 + b_3 + ...) * b_1! *
4^(b_2 + b_3 + b_4 + ...) * b_2! * ...

X = product(b_i!) * 4^(sum(i * b_i)) mod 5

=== 5 ===
別忘了， Q mod 5 = X * 3^a_5 mod 5

a_5 = [n / 5] + [n / 5^2] + [n / 5^3] + ...

= b_1 + b_2 * 5 + b_3 * 5^2 + ...
+ b_2 + b_3 * 5 + b_4 * 5^2 + ...
+ ...

而且，3^4 mod 5 == 1 ==> 3^a_5 mod 5 == 3^(a_5 mod 4) mod 5

a_5 mod 4 的時候，剛剛的 b_i * 5^k 的 5^k 又不見啦!!!

a_5 mod 4 = sum(i * b_i) mod 4

Q mod 5 = X * 3^sum(i * b_i) mod 5
= product(b_i!) * 4^sum(i * b_i) * 3^sum(i * b_i) mod 5

3^m * 4^m mod 5 = 12^m mod 5 = 2^m mod 5

Q mod 5 = product(b_i!) * 2^sum(i * b_i) mod 5

=== 6 ===
現在我們有 Q mod 2 == 0 和 Q mod 5 == blahblah

Q mod 10 = 6 * blahblah mod 10

Q mod 10 = (6 * product(b_i!) * 2^sum(i * b_i)) mod 10

目前看起來沒辦法再簡化了




30! ==>
30 = 110_5
==> 6 * 1! * 1! * 0! * 2^(2 * 1 + 1 * 1) mod 10
= 6 * 1 * 1 * 1 * 2^3 mod 10 = 8

40! ==>
40 = 130_5
==> 6 * 1! * 3! * 0! * 2^(2*1 + 1*3) mod 10
= 6 * 1 * 6 * 1 * 2^5 mod 10 = 2

100! ==>
100 = 400_5
==> 6 * 4! * 0! * 0! * 2^(2*4) mod 10
= 6 * 24 * 2^8 mod 10 = 4


--