题目描述

题目定义了一个正整数 n 的 持续性 (persistence)：

1. 从 n 开始。
2. 计算 n 的各位数字的乘积，得到 n_1。
3. 计算 n_1 的各位数字的乘积，得到 n_2。
4. 重复这个过程，直到得到一个个位数 n_m。
5. 这个过程一共执行了 m 次乘法步骤，m 就是 n 的持续性。

例如，对于 679：
Step 1: 6 × 7 × 9 = 378
Step 2: 3 × 7 × 8 = 168
Step 3: 1 × 6 × 8 = 48
Step 4: 4 × 8 = 32
* Step 5: 3 × 2 = 6 (个位数，停止)
一共进行了 5 步，所以 679 的持续性是 5。

任务： 给定一个闭区间 [a, b]，找出这个区间内所有整数中，持续性最长的那个（或那些）整数。

输入： 一行，包含两个正整数 a 和 b (1 ≤ a ≤ b ≤ 10^9, b - a < 1000)。
输出：
第一行：区间 [a, b] 内整数的最长持续性。
第二行：所有具有最长持续性的整数，按升序排列，用空格分隔。行末无多余空格。

样例

输入样例：

500 700

输出样例：

5
679 688 697

(解释：在 500 到 700 之间，679、688、697 的持续性都是 5，这是该区间内的最大持续性。其他数的持续性都小于 5。)

算法分析

(模拟 + 暴力枚举)

核心思路:

题目的关键在于计算一个数的“持续性”。由于数据范围的特点 b - a < 1000，这意味着我们需要检查的整数数量最多只有 1000 个（或者精确地说是 b - a + 1 个）。这个数量级非常小，允许我们对区间 [a, b] 内的每一个整数都进行处理。

因此，最直接的算法思路就是：
1. 遍历区间 [a, b] 内的每一个整数 i。
2. 对于每个整数 i，计算它的持续性。
3. 在遍历过程中，记录下遇到的最大持续性 ans。
4. 同时，我们需要记录下所有达到这个最大持续性的整数。一种方法是使用一个数据结构（例如代码中的 vector<pair<int, int>> q）来存储每个数字 i 及其对应的持续性 t。
5. 遍历完所有 [a, b] 区间的数之后，我们就得到了最大持续性 ans。
6. 再次遍历我们存储的结果（或筛选存储的结果 q），找出所有持续性等于 ans 的那些原始数字 i。
7. 将这些数字收集起来（例如放入 vector<int> res）。
8. 根据题目要求，对这些数字进行升序排序。
9. 按照格式输出最大持续性 ans 和排序后的数字列表 res。

如何计算一个数 n 的持续性 (代码中的 get 函数)？

代码中使用了一个 lambda 函数 get 来实现这个计算：

auto get = [&](int n) {
    int step = 0; // 初始化步数（持续性）为 0
    // 循环条件：只要 n 不是个位数 (n >= 10)，就继续计算
    while (n >= 10) {
        int t = 1; // 初始化当前轮次的各位数字乘积为 1
        // 内层循环：计算当前 n 的各位数字乘积
        while (n > 0) {
            t *= (n % 10); // 将 n 的最后一位数字乘入 t
            n /= 10; // 移除 n 的最后一位数字
        }
        // 内层循环结束后，t 中存储了原 n 的各位数字乘积
        n = t; // 将 n 更新为这个乘积，准备下一轮计算
        step++; // 完成了一步乘法计算，步数加 1
    }
    // 当 n < 10 时，循环结束，返回总步数 step
    return step;
};

这个 get 函数精确地模拟了题目中定义持续性的过程。外层 while 控制迭代步骤，内层 while 计算单步的数字乘积。

整体流程串联 (代码 main 函数)：

1. 读入 a 和 b。
2. 初始化 ans = 0 用于记录最大持续性。
3. 创建 vector<pair<int, int>> q 来存储 {持续性, 原始数字} 对。
4. 循环 i 从 a 到 b：
   • 调用 t = get(i) 计算 i 的持续性。
   • 将 {t, i} 存入 q。
   • 更新 ans = max(ans, t)。
5. 循环结束后，ans 就是最大持续性。输出 ans。
6. 创建 vector<int> res 用于存储具有最大持续性的数字。
7. 遍历 q 中的每一个 pair {x, y}（其中 x 是持续性，y 是原始数字）：
   • 如果 x == ans，说明数字 y 具有最大持续性，将其加入 res。
8. 对 res 中的数字进行升序排序 sort(res.begin(), res.end());。
9. 输出 res 中的数字，注意格式控制：
   • 使用 cout << c << " \n"[c == res.back()]; 这个技巧。
   • 对于 res 中的每个元素 c：
     • 如果 c 是最后一个元素 (c == res.back() 为真，结果是 1)，则输出 c 后面跟着 " \n"[1]，即换行符 \n。
     • 如果 c 不是最后一个元素 (c == res.back() 为假，结果是 0)，则输出 c 后面跟着 " \n"[0]，即空格 。
   • 这样就实现了数字间用空格分隔，且行尾没有多余空格，最后是换行。

时间复杂度

• 设区间长度为 K = b - a + 1。由于 b - a < 1000，所以 K <= 1000。
• 对于区间内的每个数 i（最大约为 10^9），我们需要计算其持续性 get(i)。
• 计算 get(i) 的复杂度：
  • 外层 while (n >= 10) 循环的次数是 i 的持续性，记为 m_i。这个值增长非常缓慢，即使对于很大的数，持续性也通常很小（例如，已知最大的持续性是 11，对应数字 277777788888899）。对于 10^9 以内的数，持续性会更小。可以认为 m_i 是一个很小的常数，或者最多是对数级别的。
  • 内层 while (n > 0) 循环计算各位数字乘积，其运行次数等于当前 n 的位数，约为 O(log n)。
  • 所以，单次 get(i) 的时间复杂度大约是 O(m_i * log i)。
• 总的计算时间复杂度是遍历区间 K 个数，对每个数进行 get 计算：O(K * m_{max} * log b)，其中 m_{max} 是区间内最大的持续性。由于 K < 1000 且 m_{max} 非常小，log b 大约是 30（以 2 为底）或 9-10（以 10 为底），这个复杂度是非常低的，远快于 O(K^2) 或 O(b)。可以近似看作 O(K log b)。
• 存储结果：O(K)。
• 筛选结果：O(K)。
• 排序结果：O(K’ log K’)，其中 K’ 是具有最大持续性的数字数量 (K’ <= K)。最坏情况 O(K log K)。
• 输出结果：O(K’)。

主要复杂度来源于对区间内每个数计算持续性，总体复杂度约为 O((b-a) * log b) (忽略非常小的持续性因子 m_max)，这在给定的时间限制内是完全可行的。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库头文件

using namespace std; // 使用 std 命名空间
using i64 = long long; // 定义 i64 为 long long 的别名（本题未使用）

int main() {
    // 优化 C++ 输入输出流速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b; // 区间左右端点
    cin >> a >> b; // 读取 a 和 b

    // 定义一个 lambda 函数 get，用于计算一个整数 n 的持续性
    // [&] 表示按引用捕获所有外部变量（虽然这里没用到）
    auto get = [&](int n) {
        int step = 0; // 初始化持续性计数器
        // 当 n 仍然是多位数时 (>= 10)
        while (n >= 10) {
            int t = 1; // 初始化当前步骤的各位数字乘积
            // 计算 n 的各位数字乘积
            while (n > 0) {
                t *= (n % 10); // 累乘最后一位数字
                n /= 10; // 去掉最后一位数字
            }
            n = t; // 将 n 更新为计算出的乘积
            step++; // 持续性步数加 1
        }
        return step; // 返回总的持续性步数
    };

    int ans = 0; // 初始化区间内的最大持续性为 0
    vector<pair<int, int>> q; // 创建一个 vector 存储 {持续性, 数字} 对
    // 遍历区间 [a, b] 内的每一个整数 i
    for (int i = a; i <= b; i ++ ) {
        int t = get(i); // 计算 i 的持续性
        q.push_back({t, i}); // 将 {持续性 t, 数字 i} 存入 vector q
        ans = max(ans, t); // 更新找到的最大持续性 ans
    }
    cout << ans << "\n"; // 输出最大持续性

    vector<int> res; // 创建一个 vector 存储具有最大持续性的数字
    // 遍历之前存储的所有 {持续性, 数字} 对
    // C++17 结构化绑定：将 pair 的第一个元素赋给 x，第二个赋给 y
    for (auto [x, y] : q) {
        // 如果当前对的持续性 x 等于最大持续性 ans
        if (x == ans) {
            res.push_back(y); // 将对应的数字 y 加入结果列表 res
        }
    }
    // 对结果列表 res 进行升序排序
    sort(res.begin(), res.end());

    // 遍历排序后的结果列表 res
    for (auto c : res) {
        // 输出当前数字 c
        // 使用三元运算符的数组索引技巧来决定输出空格还是换行：
        // 如果 c 是 res 的最后一个元素 (c == res.back() 为 true, 即 1)，则取 " \n"[1] -> '\n'
        // 否则 (c == res.back() 为 false, 即 0)，则取 " \n"[0] -> ' '
        cout << c << " \n"[c == res.back()];
    }

    return 0; // 程序正常结束
}