资讯安全论坛下载读书程序开发数据库系统网络电子书微信学院站长学院 QQ 考试

频道栏目

C++| 安全资讯| 安全公告| 病毒预警| 人物| 企业招聘| 其他综合|

首页 > 资讯 > C++ > 正文

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

14-05-27 来源：[db:作者]

收藏我要投稿

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;
}

点击复制链接与好友分享!回本站首页

相关TAG标签

上一篇：Java 并发专题： Timer的缺陷用ScheduledExecutorService替代

下一篇：Java线程join示例详解

相关文章

热门专题推荐 vmware win7激活工具 win10激活工具 excel word office激活小马激活工具重装系统数据恢复 u盘启动工具

图文推荐

文章

推荐

· 不掉线的路由器！路由特殊技术分析！

· 如何通过路由器来控制上网

· 宽带路由器故障巧排除

· 关于忘记Cisco交换机路由器口令后如何

· 远程管理路由器注意“安全”

· 路由器端口映射的原理及设置方法介绍

· 教你用路由器日志快速定位及排除故障

· 教你设置无线路由提高无线网BT下载速

· win7激活工具

· win10激活工具

· win7激活工具旗舰版

· office2010激活密钥

· windows7激活密钥

· office2010激活工具

· 小马激活工具

· win10激活工具

热门新闻

· 锤子坚果Pro发布后，罗永浩哭了

· 想实习的大学党看过来!这些科技巨头最

· 罗永浩锤子发布会抢先消息：锤子科技新

· Google新一代系统Fuchsia OS界面曝光

· 中国唯一连续运营20余年的网络游戏，还

· iPhone都便宜了为何国产手机越来越贵

· 丢人！谷歌和Facebook竟被虚假企业电邮

· 中国移动支付震惊日本网友为什么美国

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站