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

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 104.132.150.77 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1577458297.A.B66.html ※ 编辑: stimim (1.163.204.160 台湾), 09/07/2021 23:43:17