202412-奇妙数字(luogu-B4070)

GESP C++ 2024年12月五级真题，数论和贪心思想考点，又见质因数分解，5级似乎很喜欢考这个题型，题目难度⭐⭐⭐☆☆，五级正常难度。洛谷难度等级普及/提高−

luogu-B4070 [GESP202412 五级] 奇妙数字

题目要求

题目描述

小杨认为一个数字 $x$ 是奇妙数字当且仅当 $x=p^a$，其中 $p$ 为任意质数且 $a$ 为正整数。例如，$8=2^3$，所以 $8$ 是奇妙的，而 $6$ 不是。

对于一个正整数 $n$，小杨想要构建一个包含 $m$ 个奇妙数字的集合 $\{x_1,x_2,\cdots,x_m\}$，使其满足以下条件：

• 集合中不包含相同的数字。
• $x_1\times x_2\times \cdots\times x_m$ 是 $n$ 的因子（即 $x_1,x_2,\cdots,x_m$ 这 $m$ 个数字的乘积是 $n$ 的因子）。

小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

输入格式

第一行包含一个正整数 $n$，含义如题面所示。

输出格式

输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。

输入输出样例 #1

输入 #1

128

输出 #1

3

说明/提示

样例解释

关于本样例，符合题意的一个包含 $3$ 个奇妙数字的集合是 $\{2,4,8\}$。首先，因为 $2=2^1$，$4=2^2$，$8=2^3$，所以 $2,4,8$ 均为奇妙数字。同时，$2\times 4\times 8=64$ 是 $128$ 的的因子。

由于无法找到符合题意且同时包含 $4$ 个奇妙数字的集合，因此本样例的答案为 $3$。

数据范围

对于 $100\%$ 的数据，保证 $2\le n\le 10^{12}$。

题目分析

解题思路

1. 问题本质
   给定正整数 $n\le 10^{12}$，求其质因数分解后，每个质数 $p$ 的指数 $e$ 最多能拆成多少组互不相同的正整数之和（即 $1+2+\cdots+k\le e$ 的最大 $k$）。
   最终答案为所有质数对应 $k$ 的总和——这就是能选出的“奇妙数字”的最大个数。

2. 关键观察

   • 奇妙数字只能是 $p^k$（$p$ 为质数，$k\ge 1$）。
   • 对于同一个质数 $p$，若其总指数为 $e$，则我们最多能选出 $k$ 个互不相同的 $p^1,p^2,\dots,p^k$，满足 $1+2+\cdots+k\le e$。
     贪心：从 $k=1$ 开始依次消耗指数，直到剩余指数不足下一个 $k+1$ 为止。
   • 不同质数之间互不影响，直接累加各自的 $k$ 即可。

3. 算法步骤

   1. 对 n 做质因数分解，得到 std::map<long long, int> factor_mp 存储的 {(p1,e1),…,(pt,et)}。

   2. 对每个 (p,e)，计算最多能拆出的组数 k：

      int k = 0;
      while (e >= k + 1) {
          ++k;
          e -= k;
      }

      累加 k 到总答案。

   3. 最终输出累加后的总 k 即为答案。

4. 复杂度

   • 时间：$O(\sqrt{n})$，试除法分解质因数。
   • 空间：$O(\log n)$，仅存储质因子及其指数。

示例代码

#include <iostream>
#include <map>

int main() {
    long long n;                       // 读入待分解的正整数 n（2 ≤ n ≤ 1e12）
    std::cin >> n;
    std::map<long long, int> factor_mp; // 用 map 存储质因子及其出现次数（自动按质数升序）
    // 试除法：从小到大枚举可能的质因子 i
    for (long long i = 2; i * i <= n; i++) {
        int times = 0;                 // 统计当前质数 i 的幂次
        while (n % i == 0) {             // 能整除就继续除
            times++;
            n /= i;
        }
        if (times > 0) {                 // 若 i 确实是质因子，记录
            factor_mp.insert({i, times});
        }
    }
    // 若剩余 n > 1，则它本身是一个大于 sqrt(原 n) 的质因子
    if (n > 1) {
        factor_mp.insert({n, 1});
    }

    int count = 0;                       // 统计最多能选出的“奇妙数字”个数
    // 对每个质因子 p^e，我们要把它拆成尽可能多的互不相同的 p^k 形式
    // 贪心策略：依次选 p^1, p^2, p^3…，直到把 e 用完
    for (auto &f : factor_mp) {
        int total_times = f.second;      // 该质数的总幂次
        for (int i = 1; i <= total_times; i++) {
            count++;                     // 选了一个 p^i
            total_times -= i;            // 消耗掉 i 次幂
        }
    }
    std::cout << count;                // 输出最多能选出的奇妙数字个数

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号