GESP 题解库 / 5 级题解 / [GESP202412 五级] 奇妙数字 · 第 21 / 23 题
GESP202412 五级 · B4070 · 中等

奇妙数字

选出尽量多的互不相同"质数幂",使其乘积整除 n。

📊
n 可较大
数值范围
🔢
long long
数值类型
⚡
O(√n)
时间复杂度
🎯
分质数独立贪心
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

若 x = p^a(p 为质数、a 为正整数),则称 x 是奇妙数字。如 8 = 2³ 是奇妙的,而 6 不是。

对于一个正整数 n,要构造一个包含 m 个奇妙数字的集合 {x₁, x₂, …, x_m},满足:

求 m 的最大值。

💡
人话翻译:把 n 分解质因数后,每个质数可以独立处理——因为不同质数的幂之间互不影响。对某个指数为 e 的质数 p,我们能选的奇妙数字是 p¹, p², p³, …(各不相同),它们的指数之和不能超过 e。为了让个数最多,就取 1 + 2 + 3 + … + k ≤ e 的最大 k。答案就是各质数贡献之和。

🔍 关键词提取

质因数分解独立子问题等差数列求和贪心

已知条件

项目说明
输入一个正整数 n
输出集合最多能包含的奇妙数字个数
奇妙数字p^a(p 质数,a ≥ 1)
约束 1集合内元素互不相同
约束 2所有元素的乘积整除 n

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 分质数独立 + 取最小指数
🔬 分解
n 分解为 ∏pᵉ
每个质数 p 的指数为 e
不同质数互不干扰
可以分别最大化
🎯 单个质数
可选 p¹、p²、…
要互不相同
指数之和 ≤ e
取 1+2+…+k 使 k 最大
📐 公式
k(k+1)/2 ≤ e
k = 最大的可行值
答案 = Σ k(eᵢ)
用循环累加即可
⚠️ 易错点
以为要输出乘积(其实是个数)
忽略"互不相同"
用 int 处理大 n
忘了每个质数至少可以取 1 个
03
样例手算推导
样例与几个小例子的验证

🧮 样例:n = 128,答案 3

128 = 2⁷,只有一个质数 2,指数 e = 7。

1
可行性分析

可选的奇妙数字:2, 4, 8, 16, 32, …(即 2¹, 2², …)

选 k 个的话,指数之和至少是 1 + 2 + … + k = k(k+1)/2

要求这个和 ≤ 7

求最大的 k

2
逐个试

k = 3 时:1 + 2 + 3 = 6 ≤ 7 ✅

k = 4 时:1 + 2 + 3 + 4 = 10 > 7 ❌

所以最多取 3 个

✅ k = 3

3
构造一组方案

取 {2, 4, 8} = {2¹, 2², 2³}

乘积 = 2^(1+2+3) = 2⁶ = 64

64 整除 128 ✓

共 3 个元素

✅ 输出 3

答案 3 ✓

🔑
为什么取 2, 4, 8 而不是 2, 4, 8, 16?因为后者指数和是 1+2+3+4 = 10 > 7,乘积 2¹⁰ = 1024 不整除 128。注意 128 = 2⁷,所以任何整除 128 的数的 2 的指数最多是 7。

🧮 几个小例子的验证

用不同 n 检验"分质数独立相加"这个结论。

n分解各质数指数 e各自最大 k答案
22¹e₂ = 1k(1) = 11
62 × 3e₂ = 1, e₃ = 11 + 12
122² × 3e₂ = 2, e₃ = 11 + 12
362² × 3²e = 2, 21 + 12
642⁶e₂ = 6k(6) = 3(1+2+3=6)3
1282⁷e₂ = 7k(7) = 3(6 ≤ 7 < 10)3
10242¹⁰e₂ = 10k(10) = 4(1+2+3+4=10)4
1(无质因子)——0
1
验证 6:为什么答案不是 1?

n = 6 = 2 × 3

质数 2 可以贡献 1 个(取 2)

质数 3 也可以贡献 1 个(取 3)

集合 {2, 3},乘积 6 整除 6 ✓

共 2 个

✅ 答案 2

2
验证 12:为什么也是 2?

n = 12 = 2² × 3,e₂ = 2

k(2):1 ≤ 2 但 1+2 = 3 > 2 → k = 1

质数 3 贡献 1 个

方案 {4, 3}(=2² 和 3¹),乘积 12 整除 12 ✓

共 2 个。能不能 3 个?需 3 个互异奇妙数字,可选 {2,3,4} 乘积 24 ∤ 12 ❌

✅ 答案 2

3
验证 1024

1024 = 2¹⁰

1 + 2 + 3 + 4 = 10 ≤ 10 ✅

1 + 2 + 3 + 4 + 5 = 15 > 10 ❌

所以 k = 4,取 {2, 4, 8, 16}

乘积 2¹⁰ = 1024 恰好整除自身 ✓

✅ 答案 4

⚠️
两个容易混淆的点:① 输出的是元素个数,不是乘积;② 每个质数至少可以贡献 1 个(只要它的指数 e ≥ 1,就能取该质数本身),所以"含有不同质数越多,答案越大"这一点要意识到——n = 30 = 2×3×5 的答案就是 3。
04
解法对比
分质数贪心 vs 动态规划/搜索

⚔️ 解法对比

🟢 分质数独立贪心(推荐) 推荐

每个质数取使 1+2+…+k ≤ e 的最大 k,再相加

  • 时间 O(√n)
  • 只需分解质因数
  • 每个质数内层循环极小(k ≈ √(2e))
  • 代码 20 行
💡
为什么贪心最优:要在一个质数上塞进尽量多的元素,当然用"指数最小"的那些(即 1, 2, 3, …)。任何其他选择都会用掉更多指数、装下更少的元素。而不同质数相互独立,所以各自取最大再相加就是全局最优。

🟠 枚举所有奇妙数字后背包

把 n 的所有质数幂作为物品,做 0/1 背包

  • 物品数可能较多
  • 约束是"各质数指数分别不超过 e"(多维背包)
  • 无法用一维背包
  • 实现复杂且没必要
⚠️
为什么背包不合适:本题的约束是按质数分别限制的,属于多维约束;而由于各维完全独立,直接分解成多个一维子问题分别贪心即可。这体现了"发现变量独立性"的威力。

📈 性能对比

方案复杂度代码量
分质数贪心O(√n)约 20 行
多维背包很高约 50 行
05
算法流程图
分解质因数后逐质数贪心计数
开始读入 n;ans = 0i 从 2 试到 i × i ≤ nn 是否被 i 整除?是 ✓统计指数 e;令 k = 0,当 1+2+…+(k+1) ≤ e 时 k 加 1;ans += k否 ✗i 加 1循环结束后 n 是否大于 1?是 ✓说明剩一个质数,指数为 1,ans += 1否 ✗不处理输出 ans结束i 加 1 继续试除
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 最多奇妙数字个数

输入一个正整数 n,程序会分解质因数并给出最多能选的奇妙数字个数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    scanf("%lld", &n);

    long long ans = 0;

    // 分解质因数
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int e = 0;
            while (n % i == 0) { n /= i; e++; }   // 统计指数

            // 找最大的 k 使 1 + 2 + ... + k <= e
            int k = 0, sum = 0;
            while (sum + k + 1 <= e) {
                k++;
                sum += k;
            }
            ans += k;
        }
    }

    // 剩下的大质因子,指数为 1
    if (n > 1) ans += 1;

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么"剩下的 n > 1"只加 1?因为循环结束后如果 n > 1,说明它必是质数,且指数恰好为 1(否则早就在 √n 范围内被除掉了)。指数为 1 时最多只能取 1 个(就是该质数本身),所以直接 ans += 1。这与"质因数分解的收尾"完全一致。

📖 关键几行怎么看

代码作用为什么这样写
while (n % i == 0) { n /= i; e++; }统计指数把该质数的指数算出来
while (sum + k + 1 <= e) { k++; sum += k; }求最大 k保证 1+2+…+k ≤ e 的最大 k
ans += k累加贡献每个质数独立贡献
if (n > 1) ans += 1;收尾剩余大质数指数为 1,贡献 1 个
⚠️
三个坑:① 用 int 读入 n(可能较大);② 求 k 时把条件写成 sum + k + 1 <= e 之外的形式导致多算或少算;③ 忘记收尾的 if (n > 1) ans += 1。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
1283题面样例:128 = 2⁷ → k = 3
10无质因子,只能取空集
212 = 2¹ → k = 1
626 = 2 × 3 → 1 + 1 = 2
12212 = 2² × 3 → k(2)=1,k(1)=1,合计 2
64364 = 2⁶ → 1+2+3 = 6 ≤ 6 → k = 3
102441024 = 2¹⁰ → 1+2+3+4 = 10 → k = 4
30330 = 2 × 3 × 5,三个质数各贡献 1
✅
自查清单:① 每个质数独立算吗?② k 的条件是 1+2+…+k ≤ e 吗?③ 收尾加 1 了吗?

🚨 易错点清单

⚠️
用 int:n 可能较大,应用 long long。
⚠️
忘记收尾:循环结束后若 n > 1,该质数指数为 1,贡献 1 个。
⚠️
误解为求乘积:题目要的是集合中元素个数。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(√n)
空间复杂度
O(1)
n 范围
可较大
内层循环
k ≈ √(2e)

时间怎么算的?

空间都用在哪?

只用几个变量。

✅ 分解是主要开销,瞬间完成。关键洞察是"不同质数相互独立",把问题拆成独立的子问题。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 本题核心:按质数独立 + 每个质数取最小指数集合
// 对指数 e,最大 k 满足 k(k+1)/2 <= e
// 直接循环累加(或解方程 k = floor((-1 + sqrt(1 + 8e)) / 2))

int maxK(int e) {
    int k = 0, sum = 0;
    while (sum + k + 1 <= e) { k++; sum += k; }
    return k;
}

// 主流程
long long ans = 0;
for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
        int e = 0;
        while (n % i == 0) { n /= i; e++; }
        ans += maxK(e);
    }
}
if (n > 1) ans += 1;

// 类似"按维度独立"的问题
// - 本题:按质数维度独立
// - 数位 DP:按位维度独立
// - 网格问题:按行列独立

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
独立维度分解不同质数互不干扰所有"多质数约束"的计数题
最小代价原则用 1,2,3,… 最省预算在预算下最大化"件数"的贪心
等差数列求和1+2+…+k = k(k+1)/2所有涉及"最少用多少个名额"的题
🌟
思考题:如果题目改成"集合中元素必须两两互质"(仍然是质数幂,且乘积整除 n),答案会变吗?(提示:不会变——因为同一个质数的不同幂(如 2 和 4)并不互质(gcd = 2 > 1),所以每个质数只能取一个元素;那答案就等于"n 的不同质因子个数"。约束条件的微小变化会完全改变结论,这就是"读题要精"的重要性。)