alan23273850 的刷題筆記
d715: 階乘 -- 最後一位非零數(進階版)
Tags: math
出處：https://zerojudge.tw/ShowProblem?problemid=d715
提交：https://zerojudge.tw/Submissions?problemid=d715&account=allllllan123456
問題：給定一個 int 的正整數 n，請問階乘 n! 的最後一位非零數字為何？
解法：參考資料所寫的解法非常具技巧性！首先認知到末尾的 0 必定是由 2 和 5 所構成，所以過程中我們把所有 5 的倍數都各抽一個 5 出來，那麼 $n! = f(n)\cdot\lfloor n/5\rfloor!\cdot 5^{\lfloor n/5\rfloor}$，其中 $f(n)$ 代表 0 到 n 排除所有 5 的倍數的正整數乘積，從這個式子來看，只要知道 $f(n)$ 的末尾和 $\lfloor n/5\rfloor!$ 的末尾非零數，相乘之後再從中拉出 $2^{\lfloor n/5\rfloor}$ 和剩下的 $5^{\lfloor n/5\rfloor}$ 合併 (根據觀察可以知道 2 的個數一定比 5 還要多)，最後的末尾非零數就是答案！這邊還有個重要技巧就是要怎麼推算對一個有許多 2 的因數但不含 5 的因數的正整數 (僅知末尾) 除以 2 之後，如果還是 2 的倍數，它的新末尾是多少。其實分情況討論即可，2 除以 2 只可能是 1 或 6，但是 1 的話就不可能再是 2 的倍數，所以結果只能是 6；那 6 除以 2 只可能是 3 或 8，但是一樣 3 的話就不可能再是 2 的倍數，所以結果只能是 8；而 8 除以 2 只可能是 4 或 9，一樣 9 的話就不可能再是 2 的倍數，所以結果只能是 4；最後 4 除以 2 的話只可能是 2 或 7，一樣 7 就不可能是 2 的倍數，所以結果只能是 2；總結來說對一個「不含因數 5 的永偶數」一直除以 2 得到的末尾便是一個 2 -> 6 -> 8 -> 4 的循環。另外 $f(n)$ 末尾的規律也是非常巧合，程式碼 last 陣列儲存的是 $f(0)$ 到 $f(9)$ 的末尾，我們可以發現到 $f(9)$ 末尾是 6，而 6 乘以 6 還是 6，好好利用這個特性就可以歸納出，如果 $n\ge10$，此時 $f(n)$ 末尾便直接是 6 乘以 $f(n\%10)$ 末尾。於是程式碼中的 now 負責記錄每個子問題累積下來的 $f(n)$ 末尾，fives 負責記錄全部子問題總共拉出了幾個 5 的因數，即各階段 $\lfloor n/5\rfloor$ 的總和，最後再根據拉出的 5 的個數來決定 now 的回推次數，就能得到最終的非零末尾！
附註：
[1] https://blog.csdn.net/LuckilyYu/article/details/2078993
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n;
6 int last[] = {1,1,2,6,4,4,4,8,4,6};
7 int twos[] = {6,8,4,2};
8 while (cin >> n) {
9 if (n == 1) cout << "1\n";
10 int fives = 0;
11 int now = 1 + 5 * (n>=10);
12 while (n) {
13 now = now * last[n%10] % 10;
14 n /= 5;
15 fives += n;
16 }
17 for (int i=0; i<4; i++)
18 if (twos[i] == now) {
19 cout << twos[(i+fives) % 4] << '\n';
20 break;
21 }
22 }
23 return 0;
24}