51Nod--1003 阶乘后面0的数量

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1003

n的阶乘后面有多少个0? 6的阶乘 = 1*2*3*4*5*6 = 720,720后面有1个0。 Input 一个数N(1 <= N <= 10^9) Output 输出0的数量 Input示例 5 Output示例 1

写几个数字模拟一下,应该能发现,阶乘中后面0由2*5=10产生,即0的个数和偶数的个数和5和5的因子的个数有关,明显,偶数个数多于5和5的因子个数,所以只需要把数不断拆成5的倍数就行了。

一般的论证过程可得: 1、 每隔5个,会产生一个0,比如 5, 10 ,15,20.。。 2 、每隔 5×5 个会多产生出一个0,比如 25,50,75,100 3 、每隔 5×5×5 会多出一个0,比如125.

所以100!末尾有多少个零为:100/5+100/25=20+4=24那么1000!末尾有多少个零呢?同理得: 1000/5+1000/25+1000/125=200+40+8=248

下面是代码:

#include <iostream>
using namespace std;

int main() {
    int n, res = 0;
    cin >> n;
    // 把数不断拆成 5 的倍数
    while(n >= 5) {
        res += n/5;
        n /= 5;
    }

    cout << res << endl;

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券