奇妙数字 题解

题目分析

我们需要从正整数 $n$ 的因子中，选出尽可能多的奇妙数字（即单个质数的正整数次幂，如 $p^1, p^2, p^3, \dots$），满足：

1. 集合中没有重复数字；
2. 所有选出数字的乘积是 $n$ 的因子；
3. 集合的元素个数尽可能多。

注意到奇妙数字的形式决定了每个数字只与一个质数有关。因此，不同质数对应的奇妙数字相互独立，我们可以分别考虑 $n$ 的每一个质因子。

解题思路

设 $n$ 的质因数分解为：

对于第 $i$ 个质数 $p_i$，我们可以选取的奇妙数字只能是 $p_i^{a}$ 的形式，其中 $a$ 为正整数，且所有选中的 $a$ 必须互不相同。设选出的指数集合为 $\{a_1, a_2, \dots, a_m\}$，则乘积中 $p_i$ 的指数和为 $a_1 + a_2 + \dots + a_m$，为了使乘积仍是 $n$ 的因子，必须满足：

我们的目标是在该质数上选出尽量多的奇妙数字，也就是选出尽量多个互不相同的正整数 $a$，使得它们的和不超过 $e_i$。

要使得个数最大，显然应该优先选择最小的指数值，即 $1, 2, 3, \dots$。因为如果可以用更小的指数替换某个较大的指数，总和会变小但个数不变，可能还能再加入一个数字。因此贪心策略是最优的：

从 $1$ 开始，依次尝试选取 $1, 2, 3, \dots$，直到当前剩余指数不足以支付下一个数为止。所选数字的个数就是该质数能贡献的最大奇妙数字数量。

由于各个质数之间互不影响，最终的答案就是所有质数对应的最大个数之和。

举例说明

以 $n = 128 = 2^7$ 为例：

• 指数 $e = 7$。
• 贪心选取：$1$（余 $6$），$2$（余 $4$），$3$（余 $1$），下一个 $4$ 无法选取。
• 共选出 $3$ 个，对应奇妙数字 $2^1,22,2^3$（即 $2,4,8$），乘积 $2^{1+2+3}=26=64$，是 $128$ 的因子，且不能再多。

对于多质数的情况，例如 $n = 72 = 2^3 \times 3^2$：

• $p=2,e=3$：选 $1,2$，个数 $2$。
• $p=3,e=2$：选 $1$，个数 $1$。
• 总个数 $=2+1=3$。

算法说明

1. 初始化答案 $ans = 0$。
2. 对 $i$ 从 $2$ 到 $\sqrt{n}$ 枚举可能的质因子：
   • 若 $i$ 能整除 $n$，则计算该质数的指数 $cnt$（不断除以 $i$ 直到不能整除）。
   • 调用函数 calc(cnt) 计算该质数能选出的最多奇妙数字个数，累加到 $ans$。
3. 枚举结束后，若 $n>1$，说明剩下的 $n$ 是一个大于 $\sqrt{n}$ 的质数，其指数为 $1$，累加 calc(1)。
4. 输出 $ans$。

函数 calc(x) 的实现：

• 参数 $x$ 表示指数上限 $e$。
• 用变量 $tmp$ 从 $1$ 开始递增，表示当前尝试选取的指数 $a$。
• 只要 $x \ge tmp$，就选出该数，个数加 $1$，并从 $x$ 中减去 $tmp$，然后 $tmp$ 自增 $1$。
• 循环结束后返回选取的个数。

时间复杂度分析

• 枚举质因子的循环从 $2$ 到 $\sqrt{n}$，时间复杂度为 $O(\sqrt{n})$。
• 对于 $n \le 10^{12}$，$\sqrt{n} \le 10^6$，可以在 1 秒内轻松完成。
• 每次 calc 的复杂度与指数大小相关，但指数之和不超过 $\log_2 n$，几乎可视为 $O(1)$。
• 总时间复杂度：$O(\sqrt{n})$。

参考代码

以下是 C++ 实现，附有详细注释。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3#define ll long long
4
5// 计算当指数上限为 x 时，最多能选出多少个奇妙数字
6ll calc(ll x) {
7    int ans = 0;      // 选取的个数
8    ll tmp = 1;       // 当前尝试选取的指数
9    while (x >= tmp) {
10        ans++;
11        x -= tmp;     // 消耗掉这部分指数
12        tmp++;        // 下一个指数需要更大
13    }
14    return ans;
15}
16
17int main() {
18    ll n;
19    cin >> n;
20
21    ll ans = 0;
22    // 枚举可能的质因子
23    for (ll i = 2; i * i <= n; i++) {
24        if (n % i == 0) {
25            int cnt = 0;
26            // 计算该质因子的指数
27            while (n % i == 0) {
28                cnt++;
29                n /= i;
30            }
31            ans += calc(cnt);
32        }
33    }
34    // 如果 n 还大于 1，说明剩下一个质因子，指数为 1
35    if (n != 1) {
36        ans += calc(1);
37    }
38
39    cout << ans << "\n";
40    return 0;
41}

代码解释

• calc 函数利用贪心策略，从 $1$ 开始依次累加，返回可选取的最大个数。
• 主函数中，for 循环枚举 $2$ 到 $\sqrt{n}$ 的数，若遇到因子则统计指数并累加答案，同时将该因子除尽。这种方法能够保证每次遇到的一定是质数（因为从小往大除，合数因子早已被其质因子除尽）。
• 最后判断 n != 1 的情况，处理可能剩下的大质数，指数为 $1$。
• 累加结果即为题目所求。