求 n! 的尾部連續的 0 的個數
這個題目在網上的一個面試題中出現過
《編程之美》里也有這個問題
求末尾有多少 0
關鍵是對 n! 進行質因數分解，分解得到的質因數有 1 2 3 5 7 11 ...
觀察這些質因數我們可以知道 0 是由 2 和 5 相乘得到的
質因數 2 的個數和 5 的個數決定了 0 的個數
2 的個數大于等于 5 的個數
這里 0 的個數即是質因數中 5 的個數
對 1 - n 的每個數，計算其內有多少個質因數 5 ，所得的結果即是 n! 的尾部連續的 0 的個數。
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) 編輯 收藏 引用