Re: [問題] 100!的結尾

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者stimim (史提米)時間6年前 (2019/12/27 22:51)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/3 (看更多)

※ 引述《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://www.ptt.cc/bbs/puzzle/M.1577458297.A.B66.html