首先，這里是原題目：
寫一個(gè)程序，計(jì)算N!以10進(jìn)制數(shù)形式表示的數(shù)中最右的非零數(shù)字，并找出在它有邊又幾個(gè)零。
（程序應(yīng)適用于N <= 30000的正整形數(shù)）
方案1 ——fail
那么，拿到這個(gè)題目，我首先給出了我的第一個(gè)程序，由于這個(gè)程序很快就被刪掉重寫，所以這里就不拿出來展示，只簡單講一講邏輯。
首先，輸入N；隨后for循環(huán)計(jì)算N的階乘；再用while循環(huán)從得數(shù)的最右邊開始，尋找非零數(shù)字，并且一邊找，一邊記錄0的個(gè)數(shù)。
這一程序?qū)τ谳^小的N值而言是沒有問題的，比如題目中給出的示例12，由于12的階乘僅為479001600，所以在程序運(yùn)行時(shí)并不會(huì)出現(xiàn)問題。
但一旦N開始變大，變量fac（階乘結(jié)果）就無法儲(chǔ)存階乘后的值了，所以，我開始思考新的解決方法。
方案2——fail
階乘末尾零的個(gè)數(shù)是可以通過計(jì)算得出的，所以，我可以用這樣的方式在程序開頭計(jì)算出末尾零的個(gè)數(shù)：
int ..., five = 1;
while(pow(5, five) <= n){
zeros += n / int(pow(5, five));
five++;
}
由于階乘結(jié)果中，5的因子必然比2少，所以這里不需要考慮2，可以直接計(jì)算因子5的個(gè)數(shù)，便能知道末尾零的個(gè)數(shù)。
隨后，知道了末尾0的個(gè)數(shù)，我們就可以知道我們要求的最末非零數(shù)字在倒數(shù)第幾位了，這樣，我們就能夠抹掉計(jì)算過程中前面的位數(shù)，只考慮需要使用的最末幾位即可。完整的程序如下：
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n, zeros = 0, fac = 1, five = 1;
cin >> n;
while(pow(5, five) <= n){
zeros += n / int(pow(5, five));
five++;
}
for(int i = 2; i <= n; i++){
fac *= i;
fac = fac % int(pow(10, zeros + 1));
}
cout << fac / pow(10, zeros) << " " << zeros;
return 0;
}
的確，這一程序縮小了fac的值，能夠處理更大的N，但是，還不夠大。測(cè)試表明，即使將fac的類型設(shè)為long long，當(dāng)N超過30，仍會(huì)發(fā)生溢出。這離題目所要求的N <= 30000還相差太遠(yuǎn)。
大概估算一下，按照這一程序，計(jì)算30000的階乘，fac需要儲(chǔ)存超過7000位的數(shù)據(jù)，明顯不現(xiàn)實(shí)。
方案3——success
當(dāng)時(shí)腦子短路，所以把程序放了一下，先去干別的事情。然后，下午查了下教程，看了求n得階乘得最后一位非零數(shù)字 - butterflier這篇blog，雖然沒完全搞懂，其中的數(shù)組、函數(shù)也是現(xiàn)在也不能使用（盡管我會(huì)，但是老師沒教，所以不能用，我會(huì)是因?yàn)槲易詫W(xué)過，而且有python和swift的基礎(chǔ)），不過我還是從中受到了啟發(fā)。
所以，這最后的一個(gè)方案，我會(huì)在計(jì)算階乘的過程中，刪去階乘結(jié)果中的因子2和5，這樣，計(jì)算結(jié)果末尾的0就會(huì)被全部抹掉，所以，我就可以讓fac永遠(yuǎn)僅儲(chǔ)存1位的數(shù)據(jù)，計(jì)算30000便毫無問題。
#include<iostream>
using namespace std;
int main(){
int n, zeros = 0, two = 0, fac = 1, si;
cin >> n;
for(int i = 2; i <= n; i++){
// cout << i << " -> ";
si = i;
while(si % 2 == 0){ //首先去掉 i 中所有的2，因?yàn)?與5相乘后會(huì)在末尾增加零
si /= 2;
two += 1;
// cout << si << " -> ";
}
while(si % 5 == 0){ //去掉 i 中所有的5，由于因子2永遠(yuǎn)比因子5多，所以在配對(duì)的時(shí)候可以直接去掉一個(gè)2
si /= 5;
two -= 1;
zeros += 1; //與2配對(duì)后，末尾就多一個(gè)0
// cout << si << " -> ";
}
fac *= si;
fac %= 10; //只需要考慮最末尾的數(shù)
// cout << "fac: " << fac << " two: " << two << endl;
}
for(int i = 1; i <= two; i++){ //將未被配對(duì)的2乘回結(jié)果
fac *= 2;
fac %= 10;
}
cout << fac << " " << zeros;
return 0;
}
這段代碼顯然比blog中的那段代碼要簡單很多，但是我并不清楚哪段的運(yùn)行效率更高，反正不管怎么說，這道題目已經(jīng)完成了。
將調(diào)試代碼前的//去掉，你就能夠看到程序運(yùn)算的全過程。拿26舉例：
26
2 -> 1 -> fac: 1 two: 1
3 -> fac: 3 two: 1
4 -> 2 -> 1 -> fac: 3 two: 3
5 -> 1 -> fac: 3 two: 2
6 -> 3 -> fac: 9 two: 3
7 -> fac: 3 two: 3
8 -> 4 -> 2 -> 1 -> fac: 3 two: 6
9 -> fac: 7 two: 6
10 -> 5 -> 1 -> fac: 7 two: 6
11 -> fac: 7 two: 6
12 -> 6 -> 3 -> fac: 1 two: 8
13 -> fac: 3 two: 8
14 -> 7 -> fac: 1 two: 9
15 -> 3 -> fac: 3 two: 8
16 -> 8 -> 4 -> 2 -> 1 -> fac: 3 two: 12
17 -> fac: 1 two: 12
18 -> 9 -> fac: 9 two: 13
19 -> fac: 1 two: 13
20 -> 10 -> 5 -> 1 -> fac: 1 two: 14
21 -> fac: 1 two: 14
22 -> 11 -> fac: 1 two: 15
23 -> fac: 3 two: 15
24 -> 12 -> 6 -> 3 -> fac: 9 two: 18
25 -> 5 -> 1 -> fac: 9 two: 16
26 -> 13 -> fac: 7 two: 17
4 6
其實(shí)說句實(shí)話，這道題目難嗎？也還好，離信息學(xué)競(jìng)賽還遠(yuǎn)得很。經(jīng)過這一番摸索，我得出了一個(gè)結(jié)論——我好菜[doge]。
最近真的忙死了，同學(xué)也在催著改程序，我都沒時(shí)間搞，GitHub一片白色……這是部分聊天記錄（慘~）：
