求 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 阅读(343)
评论(0) 编辑 收藏 引用