题解 CF633B 【A Trivial Problem】

· · 题解

一段理解起来特别容易的代码 （目前来看是最短的)

思路

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

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

比较容易推出：当 n 为 5^{k} 的倍数时，其阶乘分解出 5 的个数即为 n-1 的阶乘分解出的 5 的个数 +k 。

由此还可以得出另一个重要结论：若找得到，则输出的数的个数必定为 5 个。

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

样例分析

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

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

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

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

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

其他的各种细节都在注释里了。

Here's the AC code.

#include<bits/stdc++.h>//万能头.
using namespace std;
int main(){
    int m,t=0;//t存储的是当前能被分解出来的5的个数.
    bool ok=0;//判断是否找到t使得t=m.
    scanf("%d",&m);//输入.
    for(int i=1;i<=5000001;i++){
        int j=i;
        while(j%5==0){
            t++;
            j/=5;
        }//分解出5.
        if(!ok&&t==m) cout<<"5\n";//找到了且未输出i就输出5.
        if(t==m){
            ok=1;
            cout<<i<<" ";
        }//输出符合要求的i.
        if(ok&&t!=m) return 0;//如果找完了就结束. 
    }
    cout<<0;//未找到就输出0.
    return 0;//结束.
}//求审核通过~

祝早日AC！