首页 > 试题广场 >

求表达式 f(n)结果末尾0的个数

[编程题]求表达式 f(n)结果末尾0的个数

热度指数：3038 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一个自然数n，求表达式 f(n) = 1! $\times$ 2! $\times$ 3! $\times$ ..... $\times$ n! 的结果末尾有几个连续的0？

输入描述:

自然数n

输出描述:

f(n)末尾连续的0的个数

示例1

输入

输出

算法知识视频讲解

白色纯度

讨论区对于大篇幅的介绍不友好，具体可见这篇博客。看完可以自己写代码， 10 行左右。

https://blog.csdn.net/weixin_42564710/article/details/97167298

class CountZero:
    def count(self, x):
        res, pre = 0, 0
        for i in range(5, x+1):
            while i%5 == 0:
                i //= 5
                pre += 1
            res += pre
        return res
k = int(input())
print(CountZero().count(k))

还有这种解法，思路值得借鉴。博客有详细讲解。

import math
n = int(input())
if n <=0:
    print(0)
else:
    res = 0
    k = int(math.log(n,5))
    for i in range(1,n+1):
        for j in range(1,k+1):
            res += i//(5**j)
    print(res)

发表于 2019-07-24 21:39:19 回复(1)

牛客用户568435


	nums=[0]



	k=0



	j=0



	n=int(input())



	for i in range(n):



	    l=len(nums)



	    if l%5==0:



	        while l%5 ==0:



	            k=k+1



	            l=l//5



	    nums.append(nums[-1]+k)



	print(nums[-1])

编辑于 2019-05-10 13:11:20 回复(0)

Polestar_a

n = int(input())
res = 0
for i in range(1,n+1):
    temp = 5
    while(i//temp>=1 ):
        res+=i//temp
        temp*=5
print(res)

发表于 2019-08-12 09:41:38 回复(0)

Coy_wuf

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        if (num < 5) {
            System.out.println(0);
        } else {
            int result = 0;
            for (int i = 5; i <= num; i++) {
                for (int j = 5; j <= i; j++) {
                    result = js(result, j);
                }
            }

            System.out.println(result);
        }
    }

    public static int js(int i, int j) {

        if (j % 5 == 0) {
            i += 1;
            i = js(i, j / 5);
        }
        return i;
    }
}

发表于 2019-05-10 16:49:26 回复(0)

造血干细胞201904021048566

思路是找到因式分解后的5的个数，因为只要出现5，就会有2*5 = 10，就会出现0；

但是明显超时了。

发表于 2019-05-10 09:28:34 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,r=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int p=5;
        while(i/p>=1){
            r += i/p;
            p *= 5;
        }
    }
    cout<<r<<endl;
    return 0;
}

发表于 2019-11-13 09:43:25 回复(0)

Python3

TS9527

求每个数的阶乘包含0的个数再加起来就行。每个数的阶乘包含0的个数可以参看相关题目的解法。

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        # Initialization
        result = 0
        # Traverse
        for num in range(1, n + 1):
            cnt = 0
            base = 5
            while num // base:
                cnt += num // base
                base *= 5
            result += cnt
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-09-02 15:14:03 回复(0)

牛客546251489号

有10才有0；一个10对应一个（2*5）；在阶乘中，有5前面一定会先有2；所有5的个数为末尾0的个数

对于f（10）有7个5，则末尾有7个0：1 *(1*2) * (1*2*3) *（1*2*3*4)*（1*2*3*4*5）* . .*（1*2*3*4*5*6*7*8*9）*（1*2*3*4*5*6*7*8*9*（2*5）） 10=2*5；10！中有2个5

import java.util.*;
public class Main {
        public static void main(String []args){
            Scanner scanner=new Scanner(System.in);
            int n=scanner.nextInt();
            int count=0;
            int sum=0;
            //4以上的阶乘中才会出现5；5的阶乘有1个5；
            //6的阶乘中5的个数就等于：5的阶乘中5的个数+6自身可以分解出5的个数
            //i的阶乘中5的个数就等于：i-1的阶乘中5的个数+i自身可以分解出5的个数
            //count是前一个阶乘中5的个数；
            //sum=5的阶乘中5的个数+6的阶乘中5的个数+...i的阶乘中5的个数=每一个阶乘中5的个数相加
            for(int i=5;i<=n;i++){
                int ret=i;
                while(ret%5==0){                   
                    //对于i的阶乘（1*2*..(i-1)*i）=((i-1)!*i)来说：之前count的数量的是i-1阶乘的个数；在count的基础上再加上i自身可以分解出5的个数，结果就为i的阶乘中的5的个数了                  
                    count++;
                    ret/=5;
                }
                sum+=count;
            }

   System.out.println(sum);
    }         
}

发表于 2022-05-29 21:10:31 回复(0)

Java

来学习的小张

import java.util.Scanner;
public class Main{
    public static int fun(int num,int n){
        int count = 0;
        while(num >= n && num % n == 0){
            count++;
            num /= n;
        }
        return count;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int num2 = 0;
        int num5 = 0;
        for(int i = 1;i <= n;i++){
            num2 += fun(i,2) * (n + 1 - i);
            num5 += fun(i,5) * (n + 1 - i);
        }
        System.out.println(num5);
    }
}

发表于 2022-04-14 16:41:54 回复(0)

Java

牛客196305255号

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
           solve(sc.nextInt());
       }
        sc.close();
    }
    public static void solve(int n) {
		int count=0;
		int sum=0;
		for(int i=5;i<=n;i++) {
			int tmp=i;
			while(tmp%5==0) {
				count++;
				tmp/=5;	
			}
			sum+=count;
		}
		System.out.println(sum);
	}
}

发表于 2021-01-28 18:04:45 回复(0)

下一次什么时候可以修改昵称

算法：动态规划，f(i) = f(i-1) + f(i!)
- f(i!)如何计算：每一个可以包含因子5的数都贡献零，贡献的个数就是包含因子5的个数
  - 1.找到第一个是5的倍数
  - 2.逐个减5往后遍历，遍历的过程中不断除5来统计末尾连续零的个数

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(zerosOfTail(n));
    }

    public static int zerosOfTail(int n) {
        if (n < 5) {
            return 0;
        }
        int[] dp = new int[n+1]; // 初始化默认为0，所以dp[1]-dp[4]已经为0了
        for (int i = 5; i <= n; i++) {
            dp[i] = dp[i-1] + zerosOfFactorial(i);
        }
        return dp[n];
    }

    public static int zerosOfFactorial(int n) {
        if (n < 5) {
            return 0;
        }
        int result = 0;
        int i = 0;
        for (i = n; i >= 5; i--) {
            if (i % 5 == 0) {
                break;
            }
        }
        for (; i >= 5; i -= 5) {
            int temp = i;
            while (temp % 5 == 0) {
                result++;
                temp /= 5;
            }
        }
        return result;
    }
}

发表于 2020-09-05 11:15:51 回复(0)

Python

孙双运201910171416106

n=int(input())
res,pre1=0,0
for i in range(5,n+1):
    while i%5==0:
        i=i//5
        pre1=pre1+1
    res+=pre1
print(res)

发表于 2020-06-23 22:51:23 回复(0)

Python

牛客652172042号

n = int(input())
c = 0
for i in range(1, n+1):
    if i >= 5:
        for j in range(1, 10):
            c = c + i//(5**(j))
            if i < (5**(j+1)):
                break
print(c)

1、对于n！来说，素因子5的个数就是n!末尾0的个数，计算公式是n/5+n/5^2 + n/5^3...
2、累加

发表于 2020-05-04 16:33:27 回复(0)

我要offer求你了

#include <bits/stdc++.h>
using namespace std;

int get_zeros(int num)
{
    int res = 0;
    while(num)
    {
        res += num/5;
        num = num/5;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    if(n<5) 
    {
        cout<<0<<endl;
        return 0;
    }
    int nums = 0;
    for(int i=5; i<=n; i++)
        nums+=get_zeros(i);
    cout<<nums<<endl;
    return 0;
}

leetcode 的原题

发表于 2019-12-31 15:14:27 回复(0)

yyyyyb

#include <iostream>

#include <vector>

usingnamespacestd;

intmain(){

intn;

cin>>n;

intres = 0;

intpre = 0;

for(inti = 1;i<=n;++i){

inttemp = 0;

intj = i;

while(j%5==0){

temp++;

j = j/5;

}

pre += temp;

res+=pre;

}

cout<<res<<endl;

}

发表于 2019-09-02 21:32:56 回复(0)

C/C++

MZiN

#include<iostream>
using namespace std;
int GetNum(int n)
{
if(n<0)
{
return 0;
}
int res=0;
while(n!=0)
{
res+=n/5;
n=n/5;
}
return re***r /> }
int main()
{
int n;
cin>>n;
int sum=0;
int k;
for(int i=1;i<=n;i++)
{
k=GetNum(i);
sum=sum+k;
}
cout<<sum;
return 0;
}

编辑于 2019-05-15 15:02:37 回复(0)

Python

GeekZW

# Python3 --- 完全通过版

# 求n!末尾有多少个0？
def get_0_number(n):
    if n<5:
        return 0
    else:
        n //= 5
        return n + get_0_number(n)

# 主函数
if __name__ == '__main__':
    try:
        while True:
            n = int(input())
            res = 0
            for i in range(1,n+1):
                res += get_0_number(i)
            print(res)
    except ValueError:
        pass

编辑于 2019-05-12 15:03:17 回复(0)

药铃

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

intmain(){

intn,m;

intsum = 0;

intcount = 0;

scanf("%ld",&n);

m = n;

for(intj = 0;m>=5;j++){

m = m/5;

count +=1;

}

for(inti = 0;i <=n ; i++){

for(intk = 1 ;k <= count ;k++)

{

sum = sum + i /(pow(5,k));

}

printf("%ld",sum);

return0;

}

发表于 2019-05-10 18:45:14 回复(1)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师小红书思维 2019 基础数学数学 Java工程师

上传者：小小

难度：

18条回答 65收藏 8439浏览

通过挑战的用户

查看代码

啊续啊霆啊厉

2023-03-14 09:06:12
秋风扫扫落叶

2022-11-01 16:56:15
曾泽昱

2022-10-20 21:35:58
muqiu

2022-10-12 23:52:22
冰冰超级棒

2022-10-09 12:58:55

求表达式 f(n)结果末尾0的个数

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题