首页 > 数学相关 > 数论应用 > 编程之美-阶乘末尾0的个数
2014
04-14

编程之美-阶乘末尾0的个数

这个题目是编程之美一书中给出的题目。

给定一个整数N,那么N的阶乘N!末尾有多少个0? 比如:N=10,N!=3628800,N!的末尾有2个0。

1) 递推

考虑阶乘的计算很容易溢出,直接计算阶乘肯定不合适。而每次相乘是否会有新的0产生,只和前一个阶乘的最后K位(注意是非0的位)有关。因此只记录前一个阶乘0的个数和最后d的K位,就可推出后面的。K其实和当前计算的N有关。我们只需保证 K>=N的位数  就可以了,并保证 计算不会溢出。所以这个算法要保证 N < 10^5

代码如下:

int countZero(int N) {
	int ans = 0;
	int maxInt = 1000000000;//10^9
	int  tmpn = N;
	while(tmpn){
		maxInt /= 10;
		tmpn /= 10;
	}
	int lastBit = 1; //保存上一个阶乘 的最后 K位数字
	for (int i = 2; i <= N; i++) {
		int cnt = 0;//新增加的0的个数
		int tmp = lastBit * i;

		while ((tmp % 10) == 0) {
			tmp /= 10;
			cnt++;
		}
		//防止计算溢出
		if (tmp > maxInt)
			tmp = tmp % maxInt;
		lastBit = tmp;
		ans += cnt;
	}
	return ans;
}

int main() {
	cout << countZero(25) << endl;
	cout << countZero(356) << endl;
	return 0;
}

 

2)数学解法

编程之美一书给出两个例如质因数的性质的解法。考虑哪些组合可以得到10即可,考虑哪些数相乘能得到10N!= K * 10M其中K不能被10整除,则N!末尾有M0。

N!进行质因数分解: N!=2X*3Y*5Z…,因为10=2*5,所以M25的个数即XZ有关。每一对25都可以得到10,故M=min(X,Z)。因为能被2整除的数出现的频率要比能被5整除的数出现的频率高,所以M=Z。其实也很好推出,1-9 中两两相乘,末位有0的话必须要有5,其它的数则是2的倍数。

int countZero(int N)
  {
    int ret = 0;
    int j;
    for(int i=1; i<=N; i++)
    {
      j = i;
      while(0==j%5)
       {
            ret++;
            j /= 5;
       }
     }
     return ret;
   }

当然还有一种解法:

    Z =[N/5] + [N/52] + [N/53] + …

    [N/5] 表示不大于N的的数中5的倍数贡献一个5, [N/52] 表示不大于N的数中52的倍数在贡献一个5……

 int countZero(int N)
  {
   int ret = 0;
   while(N)
   {
     ret += N/5;
     N /= 5;
   }
   return ret;
  }

参考:http://blog.sina.com.cn/s/blog_73428e9a0101b3nh.html


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。