首页 > 试题广场 >

有关阶乘的两个问题1

[编程题]有关阶乘的两个问题1
  • 热度指数：1452 时间限制：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

备注:
算法知识视频讲解
添加回答
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    if(n<5)
        cout<<0<<endl;
    else{
        long long res=0;
        while(n){
            res+=n/5;
            n/=5;
        }
        cout<<res<<endl;
    }
    return 0;
}

发表于 2019-09-02 21:04:29 回复(0)
pein531头像 pein531
每一对2和5就能够乘出一个0来，因此我们需要统计有多少对2和5的因子。事实上，我们只需要统计有多少个5即可，因为2的数量远远多于5。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine().trim());
        long count = 0;
        while(n > 0){
            count += n / 5;
            n /= 5;
        }
        System.out.println(count);
    }
}

发表于 2021-07-10 22:37:27 回复(0)
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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

有关阶乘的两个问题1

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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