Luogu CF633B 【A Trivial Problem】题解

发布时间 2023-07-11 09:15:18作者: Vanilla_RX

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

思路

由于末尾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.\)

//By Vanilla_RX
#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!