首页 > 试题广场 >

有关阶乘的两个问题1

[编程题]有关阶乘的两个问题1
  • 热度指数：1435 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个非负整数N，返回N!结果的末尾为0的数量


输入描述:
第一行一个整数N。


输出描述:
输出一个整数表示N!的末尾0的数量。
示例1

输入

3

输出

0

说明

3! = 6
示例2

输入

5

输出

1

说明

5! = 120
示例3

输入

1000000000

输出

249999998

备注:
算法知识视频讲解
添加回答
Python
圣诞节的安徒生头像 圣诞节的安徒生 
def numOfZero(n):
    num, i = 0, 5
    while i <= n:
        num += n // i 
        i *= 5 
    return num
n = eval(input())
print(numOfZero(n))
每一对（2,5）就会产生一个0，将问题转换为：n!有多少对（2,5）
进一步将问题简化为：n!拆分成的因子中有多少个5（为什么是5，不是2，是因为2出现的频率比5高）

Z = N/5 + N/(5*5) + N/(5*5*5)…..直到N/(5的K次方)等于0
Z就表示N！末尾0的个数
公式中 N/5表示不大于N的数中能被5整除的数贡献一个5，N/(5*5)表示不大于N的数中能被25整除的数再贡献一个5…….
举例说明：
N=20，Z=20/5 + 20/25 = 4，20/5可理解为20,15,10,5这四个数每个都提供了一个5
N=25，Z=25/5 + 25/25 +25/125 = 6，25/5可理解为：25,20,15,10,5这五个数每个都提供了一个5，25/25可理解为：25 = 5*5，在25/5中提供了一个5，在25/25中又提供了一个5，即25提供了两个5
同样的125=5*5*5，125可提供三个5


编辑于 2019-08-15 10:53:14 回复(0)
提交观点

问题信息

数学 基础数学
上传者：小小
难度：
1条回答 2962浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号