小林最近遇到一個問題：“對于任意給定的一個正整數n，統計其階乘n！的末尾中0的個數”，這個問題究竟該如何解決？
-
先用n=5來解決這個問題。n的階乘即n!=5!=5*4*3*2*1=120，顯然應該為2個數相乘等于10才能得到一個結尾0，仔細遍歷1,2,3…10，發現只有2*5=10才是得到末尾0的唯一方式。
-
而n!中5的倍數個數小于2的倍數個數，所以n!的末尾的0的個數應為：n!中每個個數中5的倍數的個數之和。所以代碼如下：
#includeint main(int argc,char *argv[])
{
int n;
int sum=0;
int i, k;
printf("Pleast input a positive number: ");
scanf("%d",&n); //循環控制變量
long long multiply=1L;
int j;
for(j=n;j>=1;--j){multiply*=j;
}
printf("The factorial of %d is:%ld\n",n,multiply);
for(i=5; i<=n; i=i+5) //只有5的倍數才含5的因子
{int m=i;for(k=0; m%5==0; k++)m=m/5;sum=sum+k;
}
printf("The number of zero in %d! is: %d",n,sum);
return 0;
}
注意
這個問題的通常解法是：求出n!的值，然后再算出結尾0的個數。但這樣做有個問題，就是n!在n=13及以上時就已經非常大了，已經溢出了long long型整數所能保存的最大值。也就是說，在n=13及以上時不能用通常解法。這就是本篇文章解法的意義，這也是許多此類面試題的解法。
13！=6,227,020,800?，但下圖顯示的13！的結果為1932053504，這是溢出long long整型值后的值。
溢出示意圖如下：
-
如何計算溢出后的值是多少？
拿13！=6,227,020,800來舉例，保存它的值的數據類型為long long，大小為4個字節，最大值為2147483648，用6227020800%2147483648得出的值即為1932053504。這個值就是示例中顯示出來的結果，但它的值已被截取了。 -
如何心算出本篇文章給出的面試題？
拿26！舉例，先取出可以得出結尾0的單個數：5、10、15、20、25。再求出每個數字的以5為底的對數值的floor值，再求出這些值之和即為答案。如下圖：
微風不燥，陽光正好，你就像風一樣經過這里，愿你停留的片刻溫暖舒心。
我是程序員小迷（致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等編程技術的技巧經驗分享），若作品對您有幫助，請關注、分享、點贊、收藏、在看、喜歡，您的支持是我們為您提供幫助的最大動力。
歡迎關注。助您在編程路上越走越好！
