洛谷 P2388 阶乘之乘 题解

本蒟蒻又来发题解了QwQ;

看到这个题目,本蒟蒻第一眼就想写打个暴力;

嗯,坏习惯;

但是,动动脑子想一想就知道,普通的的暴力是过不了的;

但是,身为蒟蒻的我,也想不出什么高级的数学方法来优化;

好,回到正题
题目是要求我们求出这个累乘末尾的‘0’

‘0’是个特别特殊的数字,因为是累乘,那么一个‘0’肯定是由一个‘2’和一个‘5’相乘得来的;

而且‘0’的个数肯定是‘2’和‘5’之间数目较少的那一个的个数;

而我们又是求它的阶乘的累乘,

所以‘5’的个数一定要小于‘2’的个数
那么‘0’的个数就是‘5’的个数‘

这样就很好写的;

PS.我们有足够的时限去写这道题,那么你跑100ms过的是100分,1ms过的也是100分;那么我们就不应该盲目的去追求更快的速度,更高级的方法,应该更加有效的练习(划掉;但是有时间我觉得还是可以多想一想,可以锻炼锻炼思维。

这只代表个人观点;

好,愉快的代码时间:

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

#define int long long//不开long long见祖先 
int n, now, num, ans;//num是这一轮的‘0’的个数,ans是总答案; 
signed main()
{
    scanf("%lld", &n);//输入 
    for(int i = 1; i <= n; ++ i)//累乘,依次枚举 
    {
        now = i;//因为要不断除5,所以不可以直接用i; 
        while(now % 5 == 0)//找‘5’ 
        {
            ++ num;//加一个 
            now /= 5;//除上5 
        }
        ans += num;//相加
        //注意:num不需要赋值为0,也不可以
        //因为它的累乘包含了它的前面的点,
        //所以如果num赋值为0后就会导致错误 
    }
    printf("%lld", ans);//输出,再次强调一定要开long long 
    return 0;
}
原文地址:https://www.cnblogs.com/Flash-plus/p/12028307.html