查看: 966|回复: 5

[JavaWeb] POJ 1401 Factorial 解题报告

[复制链接]

该用户从未签到

发表于 2017-12-17 20:27:09 | 显示全部楼层 |阅读模式
以下是算法的直观解释。
假设求60!的结果后面有几个0。
由《编程之美》可知其实是求1,2,3……60中共有几个5的因子,如,5有一个,10有两个,……一起加起来即得到结果。但是如果一个一个这样计算下去,会超时的。
其实还有更简单的计算方法。
我们知道,在1->60的数中,以下的数可以被5整除:
5,10,15,20,25,30,35,40,45,50,55,60
共60/5 = 12(个)。
其中,
25,50可以被25整除,即25和50可以贡献两个5的因子。
即其中可以贡献2个5的因子的个数为60/25 = 2(个)。
贡献3个5的因子的没有了,因为60/125 = 0。
所以共有12 + 2 = 14 (个)5的因子。(即1 * 10 + 2 * 2)


Cpp代码

  • #include <iostream>  
  •   
  • using namespace std;  
  •   
  • int main()  
  • {  
  •     int T;  
  •     cin >> T;  
  •     __int64 N;  
  •     for(int i = 0; i < T; i++) {  
  •         cin >> N;  
  •         int ret = 0;  
  •         while(N) {  
  •             ret = ret + N / 5;  
  •             N = N / 5;  
  •         }  
  •   
  •         cout << ret << endl;  
  •     }  
  •   
  •     return 0;  
  • }  



您需要登录后才可以回帖 登录 | 注册青鸟豆号

本版积分规则

Copyright 1999-2018 Beijing Aptech Beida Jade Bird Information Technology Co.,Ltd

北大青鸟IT教育 北京阿博泰克北大青鸟信息技术有限公司 版权所有

京ICP备11045574号-3 京公网安备11010802013845号

快速回复 返回顶部 返回列表