首页 > 试题广场 >

末尾0的个数

[编程题]末尾0的个数

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

输入一个正整数n,求n!(即阶乘)末尾有多少个0？比如: n = 10; n! = 3628800,所以答案为2

输入描述:

输入为一行，n(1 ≤ n ≤ 1000)

输出描述:

输出一个整数,即题目所求

示例1

输入

输出

算法知识视频讲解

查看答案及解析

美团到店招聘

#include <stdlib.h>

#include <stdio.h>

using namespace std;

int main()

{

int n;

scanf("%d",&n);

//算法

int count = 0;

while(n){

count += n/5;

n /= 5;

}

printf("%d",count);

return 0;

发表于 2017-02-07 22:42:02 回复(9)

C/C++

bee🌚🌝

#include<iostream>
using namespace std;

int countFactZeros(int num) {
    int count = 0;
    if (num < 0) return -1;

    for (int i = 5; num / i > 0; i *= 5) {
        count += num / i;
    }

    return count;
}

int main() {
    int n;
    cin >> n;
    cout << countFactZeros(n) << endl;

    return 0;
}

编辑于 2017-02-05 20:39:45 回复(0)

孙强Jimmy

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt(), res = 0;
            for (int i = 5; i <= n; i *= 5) {
                res += n / i;
            }
            System.out.println(res);
        }
        in.close();
    }
}

发表于 2017-10-03 08:45:50 回复(1)

爱吃青菜皮卷面的byr

尾部所有的0都是由因子5*2得到的，
由于2.6.8 都可以视为因子2，所以因子2的个数远大于因子5的个数
所以只需要求出因子5的个数即可。
由于25,125这个数不止含有一个因子5，所以需要求完后递归调用n/5
以上。
import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(trailingZeros(n));
        
    }
    private static int trailingZeros(int n){
        return n==0?0:n/5+trailingZeros(n/5);
    }
    
}

发表于 2018-02-28 11:38:40 回复(0)

元气の悟空

#include<stdio.h>
int main(){
    int x,res=0;
    scanf("%d",&x);
    while(x) res+=x/5,x/=5;
    printf("%d\n",res);
}

发表于 2017-10-21 10:58:12 回复(0)

菜鸟四号

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,s=1,sum=0;
    cin>>n;
    for(int i=2; i<=n; i++) {
        s*=i;
       while(s%10==0){
                sum++;
                s/=10;
            }
        s%=100;
    }
    cout<<sum<<endl;
    return 0;
}

发表于 2017-08-10 11:20:16 回复(14)

Python

yzdeng

n=int(input())

fac=1
for i in range(1,n+1):
    fac*=i
fac=[x for x in '%d'%fac]
num=0
for i in fac[::-1]:
    if i!='0':
        break
    num+=1
print(num)

发表于 2018-05-28 22:15:26 回复(1)

让世界感受痛苦

from functools import *
n=int(input())
a=[int(i)for i in range(1,n+1)]#将1到n变成一个序列，以便下面的reduce函数
k=lambda x,y:x*y#定义阶乘函数
q=reduce(k,a)#reduce(function, sequence, initial)
spl=True
d=0
while spl==True:
if q%10==0:#末尾为0时
d+=1
q//=10
elif q%10!=0:#末位不为0时
spl=False
print(d)#最后结果

发表于 2020-08-02 17:20:45 回复(1)

Spectre_

#include<iostream>

using namespace std;

int main()
{
    int num, res = 0;
    cin >> num;
    while (num /= 5) res += num;
    cout << res;
    return 0;
}

发表于 2019-10-11 14:40:53 回复(0)

Java

底薪到手，关机下班

import java.util.Scanner;

public class Test03 {

    public static int getZero(int num){
        return num==0?0:num/5+getZero(num/5);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println(getZero(num));
    }
}

发表于 2019-03-18 23:36:28 回复(0)

晓色竹韵

参考牛友唐龙3bf链接：https://www.nowcoder.com/questionTerminal/6ffdd7e4197c403e88c6a8aa3e7a332a

最简单的思路就是把所有的数字进行分解质因数，例如：

6 = 2*3

15 = 3*5

64 = 2*2*2*2*2*2 = 2^6

100 = 2^2 * 5^2

576 = 2^6 * 3^2

那么我们在计算n的阶乘时，实际上就是把所有小于等于n的正整数分解成质因数，然后再将其乘到一起，那么末尾0的个数实际上就是2*5的个数，而2的个数明显是很多很多的，所以问题就转化成了5的个数。

而只有5的倍数才有5这个因数，所以，问题就进一步简化为小于等于n的数中有多少个数是5的倍数，当然25的倍数，125的倍数，625还要单独考虑。

编制以下程序：

#include <iostream>
using namespace std;

int main()
{
int n,temp,count=0;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
temp=n-i;
while(temp%5==0)
{
count++;
temp=temp/5;
}
}
cout<<count<<endl;
}
return 0;
}

编辑于 2018-07-27 10:36:25 回复(0)

萧雲

//思路：2*5=10，而乘数中2的倍数多于5的倍数，所以先求出5的倍数的个数；再求出其中5²的倍数的个数

//……

//以此类推，累加即可

#include<iostream>

using namespace std;
int main ()
{
int i,n;
cin>>n;
int x=1;
while(n!=0)
{
n=n/5;
i=i+n;
}
cout<<i;
return 0;
}

发表于 2018-07-05 22:19:38 回复(0)

深度学习ing的人


	#include <stdio.h>



	intnInNumber(intnumber, intn)



	{



	    intsum = 0;



	    while(number%n==0)



	    {



	        sum +=1;



	        number /= n;



	    }



	    returnsum;



	}



	intmain()



	{



	    intn, twoInSumN=0, fiveInSumN=0;



	    scanf("%d", &n);



	    if(n<=0)return-1;



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



	    {



	        twoInSumN += nInNumber(i,2);



	        fiveInSumN += nInNumber(i,5);



	    }



	    printf("%d", (twoInSumN>fiveInSumN) ? fiveInSumN : twoInSumN);



	    return0;



	}

发表于 2018-06-10 22:24:11 回复(0)

牵着蜗牛

import java.math.BigInteger;
import java.util.Scanner;
public class Main{
    public static void main(String []args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        BigInteger result = new BigInteger("1");
        for(int i=n;i>0;i--){
            BigInteger num=new BigInteger(String.valueOf(i));
            result=result.multiply(num);
        }
        StringBuffer sb=new StringBuffer(String.valueOf(result));
        sb.reverse();
        int count=0;
        while(sb.substring(count,sb.length()).startsWith("0")){
            count++;
        }
        System.out.println(count);
    }
}

编辑于 2018-05-31 17:21:37 回复(0)

C/C++

NB响当当

// 看了评论区的程序……原来原理是这么的高深！我用一种简单无脑的方法通过了本题

// 测试。如果有题友不是很喜欢因式分解，可以尝试我的做法。当然，我这算法不一定

// 完全正确，如果您找到了反例，回复区单聊。

// 思路：由于只需要计算结尾处0的个数，因此我们只需要知道每次相乘以后结尾有几

// 个0即可。由于100以内不会有两个非10整数相乘结尾有2个0的情况，1000以内不会

// 同类数乘有3个0的情况。因此我们可以顺序让两个数相乘，结果进行 /10 计数，所

// 得结果进行 /100 保留。保留后的数再次与后面的数相乘，依次反复，例子如下：

// 假设两个数相乘后得到 9916200 ，首先我们进行0计数，得到2，然后得到新数字99162

// 由于1000内不存在两个数相乘结尾有3个0的情况，因此我们只保留最后两位，即62，用

// 此数与下一个数相乘，依次循环。这样，即使输入1000，最后一次进行计数时最大可能

// 位数也只有 99 * 1000 = 99000 五位，int大小即可容纳。

// 下面代码我是反向写的，时间复杂度O(n)，实际运行时间3ms。

#include <iostream>
using namespace std;
int main(void)
{
int n, cont = 0, tmp = 1;
cin >> n;
while (n)
{
tmp *= n--;
while (tmp % 10 == 0)
tmp /= 10, cont++;
tmp %= 100;
}
cout << cont << endl;
return 0;
}

编辑于 2018-01-21 16:09:35 回复(0)

C/C++

nbgao

#include <iostream>

using namespace std;

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

发表于 2018-01-09 01:01:25 回复(0)

小黑君_

#include <iostream>
using namespace std;
int main()
{
    int n,cnt=0;
    cin>>n;
    while(n/=5)
    {
        cnt+=n;
    }
    cout<<cnt<<endl;
    return 0;
}

原理如下：

在满足题意的任意数列中，偶数的个数必定远远大于5的个数，而产生末尾0必须是由1个5和1个偶数组成，计算时5的个数少，偶数多，因此忽略偶数部分，只计算数列中5的个数。

需要特别注意的是，当输入的n大于5时，会开始产生隐含5的数字，对所有所有大于5的数字都需要通过除以5来把其它数字中隐含的5找出来，把所有5的个数找出来间接得出的就是最终0的个数。

编辑于 2017-12-12 22:13:33 回复(0)

ACpeppermint













	#include <iostream>



	 



	using namespace std;



	 



	int slove(int n) {



	    int num = 1;



	    int res = 0;



	    while(n / num) {



	        num *= 5;



	        res += n / num;



	    }



	    return res;



	}



	 



	int main()



	{



	    int n;



	    cin >> n;



	    cout << slove(n) << endl;



	    return 0;



	}

发表于 2017-09-15 17:58:52 回复(0)

啊咿呀嘿

<?php

$num = trim(fgets(STDIN));

function exam($n){
        $res = 0;
        for($i=$n; $i>=5; $i--){
                $tmp = $i;
                while(($tmp%5) == 0){
                        $res++;
                        $tmp /= 5;
                }
        }
        return $res;
}

//function shenqi($n){
//        $res = 0;
//        while($n){
//                $res= $res + intval($n/5);
//                $n = intval($n/5);
//        }
//        return $res;
//}

//echo shenqi($num);


echo exam($num);

发表于 2017-09-10 17:09:50 回复(0)

324134134143428

#include<iostream>
#include<algorithm>
using namespace std;
int main()
    {
    int n;
    while(cin>>n)
        {
        int sum = 0;
        while(n)
            {
            sum+=n/5;
            n/=5;
        }
        cout<<sum<<endl;
    }
    return 0;
}
//边摆摊边算出来的，求解放

发表于 2017-09-08 17:07:21 回复(0)