n！末尾0的个数

肯定不能直接求出 n! 然后在计算后边有多少个0

因为 1000000!  的位数就是 5565709

对于 n！ 的末尾如果有一个 0 的话，必然有一个 5 与其对应着

所以就是找从 1 到 n 这些数的约数（因子）中有多少个 5 

它们有几个 5,   n! 末尾就有几个0

令f(x)表示正整数x末尾所含有的“0”的个数，则有：

        f(n!) =[n/5]+[n/25]+[n/125]+[n/625]+......

        [] 表示向下取整

显然：

      当0 < n < 5时，f(n!) = 0;
      当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。

第一种，递归的形式

#include<cstdio>
int cal(int n)
{
  if(n<5)  return 0;
  n=n/5;
  return n+cal(n);
}
int main()
{
  int t,n;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n);
    printf("%d\n",cal(n));
  }
  return 0;
}

第二种，用循环来解决

#include<cmath>
#include<cstdio>
int main()
{
  int t,n;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n);
    int sum=0,c=5;
    while(n/c!=0)
    {
      sum+=n/c;
      c*=5;
    }
    printf("%d\n",sum);    
  }
  return 0;
}

也可以这样写：

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

​

题目练习:​​HDU1124​​