首页 > 试题广场 >

有关阶乘的两个问题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

备注:
#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)
每一对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)
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)