选出尽量多的互不相同"质数幂",使其乘积整除 n。
若 x = p^a(p 为质数、a 为正整数),则称 x 是奇妙数字。如 8 = 2³ 是奇妙的,而 6 不是。
对于一个正整数 n,要构造一个包含 m 个奇妙数字的集合 {x₁, x₂, …, x_m},满足:
x₁ × x₂ × … × x_m 是 n 的因子求 m 的最大值。
p¹, p², p³, …(各不相同),它们的指数之和不能超过 e。为了让个数最多,就取 1 + 2 + 3 + … + k ≤ e 的最大 k。答案就是各质数贡献之和。质因数分解独立子问题等差数列求和贪心
| 项目 | 说明 |
|---|---|
| 输入 | 一个正整数 n |
| 输出 | 集合最多能包含的奇妙数字个数 |
| 奇妙数字 | p^a(p 质数,a ≥ 1) |
| 约束 1 | 集合内元素互不相同 |
| 约束 2 | 所有元素的乘积整除 n |
p¹, p², …, p^k 最省指数(指数和 1+2+…+k 最小);所以 k 是使 k(k+1)/2 ≤ e 的最大值128 = 2⁷,只有一个质数 2,指数 e = 7。
可选的奇妙数字:2, 4, 8, 16, 32, …(即 2¹, 2², …)
选 k 个的话,指数之和至少是 1 + 2 + … + k = k(k+1)/2
要求这个和 ≤ 7
求最大的 k
k = 3 时:1 + 2 + 3 = 6 ≤ 7 ✅
k = 4 时:1 + 2 + 3 + 4 = 10 > 7 ❌
所以最多取 3 个
✅ k = 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 | 答案 |
|---|---|---|---|---|
| 2 | 2¹ | e₂ = 1 | k(1) = 1 | 1 |
| 6 | 2 × 3 | e₂ = 1, e₃ = 1 | 1 + 1 | 2 |
| 12 | 2² × 3 | e₂ = 2, e₃ = 1 | 1 + 1 | 2 |
| 36 | 2² × 3² | e = 2, 2 | 1 + 1 | 2 |
| 64 | 2⁶ | e₂ = 6 | k(6) = 3(1+2+3=6) | 3 |
| 128 | 2⁷ | e₂ = 7 | k(7) = 3(6 ≤ 7 < 10) | 3 |
| 1024 | 2¹⁰ | e₂ = 10 | k(10) = 4(1+2+3+4=10) | 4 |
| 1 | (无质因子) | — | — | 0 |
n = 6 = 2 × 3
质数 2 可以贡献 1 个(取 2)
质数 3 也可以贡献 1 个(取 3)
集合 {2, 3},乘积 6 整除 6 ✓
共 2 个
✅ 答案 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
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+2+…+k ≤ e 的最大 k,再相加
把 n 的所有质数幂作为物品,做 0/1 背包
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 分质数贪心 | O(√n) | 约 20 行 |
| 多维背包 | 很高 | 约 50 行 |
输入一个正整数 n,程序会分解质因数并给出最多能选的奇妙数字个数。
点按钮开始 →
#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 个(就是该质数本身),所以直接 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。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
128 | 3 | 题面样例:128 = 2⁷ → k = 3 |
1 | 0 | 无质因子,只能取空集 |
2 | 1 | 2 = 2¹ → k = 1 |
6 | 2 | 6 = 2 × 3 → 1 + 1 = 2 |
12 | 2 | 12 = 2² × 3 → k(2)=1,k(1)=1,合计 2 |
64 | 3 | 64 = 2⁶ → 1+2+3 = 6 ≤ 6 → k = 3 |
1024 | 4 | 1024 = 2¹⁰ → 1+2+3+4 = 10 → k = 4 |
30 | 3 | 30 = 2 × 3 × 5,三个质数各贡献 1 |
n > 1,该质数指数为 1,贡献 1 个。只用几个变量。
✅ 分解是主要开销,瞬间完成。关键洞察是"不同质数相互独立",把问题拆成独立的子问题。
// 本题核心:按质数独立 + 每个质数取最小指数集合 // 对指数 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 | 所有涉及"最少用多少个名额"的题 |