POJ 1401 && ZOJ 2202 Factorial 阶乘N!的末尾零的个数

题目地址:
POJ 1401
ZOJ 2202

题意：
求N!后面有几个0。

分析：
组合数学类型的题目。
正常的话可能会去分解1~N数里面有几个5和2，但是这样的复杂度为O(nlogn)。
其实有更巧妙的办法，可以把问题分解成子问题。
可以发现N!末尾的0与1~N中有几个5的因子相同(因为2总是比5多)。
1~N中只有5的倍数包含5因子，比如[5, 10, 15, 20...]，所以我们抽出其中每个数的一个5因子，这时候就只剩下[1, 2, 3, ...., N/5]了，其他没有5因子的就都给扔掉就行了。
你会发现新产生的这个序列又是一个相同的问题。
写出递推式就是：F(n) = n/5 + f(n/5)，可以用递归也可以用循环实现。

代码：

/*
*  Author:      illuz 
  
   
*  File:        1401.cpp
*  Create Date: 2014-05-26 20:20:53
*  Descripton:  also zoj2022
*/

#include 
   
     int n, t; int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); int ans = 0; while (n != 0) { ans += n / 5; n /= 5; } printf("%d\n", ans); } return 0; }