求 n! 的尾部連續(xù)的 0 的個數(shù)
這個題目在網(wǎng)上的一個面試題中出現(xiàn)過
《編程之美》里也有這個問題
求末尾有多少 0
關鍵是對 n! 進行質因數(shù)分解，分解得到的質因數(shù)有 1 2 3 5 7 11 ...
觀察這些質因數(shù)我們可以知道 0 是由 2 和 5 相乘得到的
質因數(shù) 2 的個數(shù)和 5 的個數(shù)決定了 0 的個數(shù)
2 的個數(shù)大于等于 5 的個數(shù)
這里 0 的個數(shù)即是質因數(shù)中 5 的個數(shù)
對 1 - n 的每個數(shù)，計算其內有多少個質因數(shù) 5 ，所得的結果即是 n! 的尾部連續(xù)的 0 的個數(shù)。
1 #include <iostream>
2 using namespace std;
3
4 int foo(int n)
5 {
6 int ret = 0, t;
7 for (int i = 1; i <= n; ++i)
8 {
9 t = i;
10 while (t % 5 == 0)
11 {
12 ++ret;
13 t /= 5;
14 }
15 }
16 return ret;
17 }
18
19 int main()
20 {
21 int n;
22 while (cin >> n)
23 {
24 cout << foo(n) << endl;
25 }
26 return 0;
27 }
posted on 2011-07-19 22:12
unixfy 閱讀(370)
評論(0) 編輯 收藏 引用