※ 引述《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