出题人题解｜智能计算器

题目大意

给定一个正整数 $m$，请你统计一共有多少个正整数 $n$ 满足，$n$ 的阶乘的末尾连续 $0$ 的数量恰好为 $m$。

输出满足条件的 $n$ 的数量以及所有满足条件的 $n$。

题意分析

要求的是正整数 $n$ 的阶乘连续末尾的 $0$ 个数，实则为计算阶乘中的数字拆分之后能凑出多少乘 $10$。

解题思路

注意到 $10=5*2$，所以我们只需要对每个数字进行分解，计算出每个数字包含的 $2,5$ 的个数。

$2, 5$ 中个数少的数就是当前个数后缀 $0$​​ 的个数。

由于是阶乘，$n!$ 中 $2$ 的个数等于 $n-1!$ 中 $2$ 的个数加上 $n-1$ 分解出来的 $2$ 的个数。$5$ 的个数同理。

时间复杂度解析

本题时间复杂度为 $O(k \cdot logk)$，$k$ 为程序找到的最大 $i$ 的值。

代码演示

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int two, five;

int main() {
  cin >> m;
  vector<int> v;
  for (int i = 1; ; i++) {
    int t = i;
    // 统计因子 2 的个数
    while (t % 2 == 0) two++, t /= 2;
    // 统计因子 5 的个数
    while (t % 5 == 0) five++, t /= 5;
    if (min(two, five) == m) v.push_back(i);
    if (min(two, five) > m) break;
  }
	
  cout << v.size() << endl;
  for (int x : v) cout << x << ' ';
  return 0;
}