CF633B A Trivial Problem 题解

· · 题解

思路

这题数据较小，可以暴力循环。 用一个变量存储当前分解出 5 的个数，直接往下找就行。

末尾 0 的个数就是阶乘中分解出 10 的个数，也就是分解出 2 的个数与 5 的个数中的最小值。

显然 5 的个数小于 2 的个数，所以找出分解出的 5 的个数。

所以可推出：当 n 为 5^{k} 的倍数时，其阶乘分解出 5 的个数即为 n-1 的阶乘分解出的 5 的个数 +k 。 所以还可以得出一个重要结论：若找得到，则输出的数的个数一定为 5 个。

这两个结论都对解题有巨大帮助。（可以看样例分析）

样例分析

末尾 0 个数为 11 的数，当找到 5 时，tb的值更新为 1 ，接下来的数末尾都为 1 个0。

当找到 10 时，t 的值更新为 2 ，接下来的数末尾 0 的个数就不为 1 了，结束。

因此输入 1 时，输出 5,6,7,8,95,6,7,8,9 共 5 个。

当找到 24 时，t = 4 ，接下来为 25 ，t=t+2=6，因此没有末尾 0 为 5 的数，输出 0 。

代码

#include<bits/stdc++.h>
using namespace std;
int m,t;//t是当前能被分解出来的5的个数
bool b;//累加是否找到t使得t=m
int main(){
   scanf("%d",&m);
   for(int i=1;i<=500000;i++)
   {
        int j=i;
        while(j%5==0)t++,j/=5;//分解出有几个5
        if(!b&&t==m)cout<<5<<endl;//找到了且没有输出i就输出5，换行 
        if(t==m){b=1;cout<<i<<" ";}//输出符合要求的i
        if(b&&t!=m)return 0;//找完了就结束
    }
    cout<<0;//一直未找到就不会结束，最后输出0
    return 0;//完美结束！
}

求通过！！！