【GESP】C++五级真题（数论-素数、贪心思想考点） luogu-B4050 [GESP202409 五级] 挑战怪物
GESP C++ 2024年9月五级真题，数论-素数、贪心思想考点，难度⭐⭐⭐☆☆，五级来说难度适中。洛谷难度等级普及/提高−
luogu-P10720 [GESP202406 五级] 小杨的幸运数字
题目要求
题目描述
小杨正在和一个怪物战斗，怪物的血量为 $h$，只有当怪物的血量恰好为 $0$ 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式：
- 物理攻击。假设当前为小杨第 $i$ 次使用物理攻击，则会对怪物造成 $2^{i - 1}$ 点伤害。
- 魔法攻击。小杨选择任意一个质数 $x$（ 不能超过怪物当前血量），对怪物造成 $x$ 点伤害。由于小杨并不擅长魔法，他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。
输入格式
本题单个测试点内有多组测试数据。第一行包含一个正整数 $t$，代表测试用例组数。
接下来是 $t$ 组测试用例。对于每组测试用例，只有一行一个整数 $h$，代表怪物血量。
输出格式
对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物， 输出 $-1$。
输入输出样例 #1
输入 #1
1
2
3
4
3
6
188
9999
输出 #1
1
2
3
2
4
-1
说明/提示
样例 1 解释
对于第一组测试用例，一种可能的最优方案为，小杨先对怪物使用魔法攻击，选择质数 $5$ 造成 $5$ 点伤害，之后对怪 物使用第 $1$ 次物理攻击，造成 $2^{1 - 1} = 1$ 点伤害，怪物血量恰好为 $0$，小杨成功击败怪物。
数据规模与约定
| 子任务编号 | 分数占比 | $t$ | $h$ |
|---|---|---|---|
| $1$ | $20\%$ | $\leq 5$ | $\leq 10$ |
| $2$ | $20\%$ | $\leq 10$ | $\leq 100$ |
| $3$ | $60\%$ | $\leq 10$ | $\leq 10^5$ |
对于全部的测试数据，保证 $1 \leq t \leq 10$，$1 \leq h \leq 10^5$。
题目分析
解题思路
- 问题本质
小杨的攻击方式只有两种：- 纯物理：第 $i$ 次伤害 $2^{i-1}$，累加到 $k$ 次时总伤害为 $2^k-1$。
- 至多一次魔法：任选质数 $x\le h$，造成 $x$ 点伤害，其余用物理补足。
目标：判断能否把 $h$ 恰好打成 $0$，并求最少攻击次数。
纯物理判定
先检查 $h$ 是否等于某个 $2^k-1$。
由于 $2^{17}-1=131071>10^5$，只需枚举 $k\le 16$ 即可。
若命中，直接返回 $k$。- “魔法+物理”枚举
若纯物理不行，则尝试“用一次魔法”。
设魔法伤害为质数 $x$，则剩余血量 $h-x$ 必须能被“纯物理”恰好耗尽。
为使总攻击次数最少，应：- 让 $x$ 尽可能大，这样 $h-x$ 尽可能小，所需物理次数 $k$ 也尽可能小；
- 从大到小枚举质数 $x$，一旦找到合法的 $(x,k)$ 组合，即可提前退出，此时总次数为 $k+1$ 必为最小。
枚举范围：$x\in[2,h]$ 中的所有质数。
单次判断 $h-x$ 是否为 $2^k-1$ 的过程与步骤 2 相同，$O(\log h)$。
质数判断优化
数据范围 $h\le 10^5$，质数个数不足 1 万，每次用 $\sqrt{x}$ 试除即可。
若值域再大，可预先用埃氏筛打出质数表，再顺序遍历质数，复杂度可降至“质数个数 × 单次判断耗时”，即 $O(\pi(h)\cdot\log h)$。其中 $\pi(h)$ 表示不超过 $h$ 的质数个数，$\log h$ 来自判断 $h-x$ 是否为 $2^k-1$ 的逐次比较。- 输出
若上述两步均失败，说明无法恰好击败怪物，输出 $-1$；否则输出最小攻击次数。
复杂度与边界
时间复杂度：
外层循环 $t$ 组数据。
对每组血量 $h$，先 $O(\log h)$ 判断“纯物理”是否可行；
再枚举所有不超过 $h$ 的质数 $x$（共 $\pi(h)$ 个），对每个质数做一次 $O(\log h)$ 的“剩余血量是否为 $2^k-1$”判定。
因此单组耗时 $O!\left(\pi(h)\cdot\log h\right)$，总复杂度
\(O\!\left(t\cdot\pi(h)\cdot\log h\right),\)
其中 $\pi(h)\approx \dfrac{h}{\ln h}$，在 $h\le 10^5$ 时约 9592 个质数，完全可接受。空间复杂度：仅用到若干整型变量与循环计数器，$O(1)$ 辅助空间。
该思路清晰、实现简短，无需高深算法，五级考生易于掌握；若进一步追求极致速度，可预先生成质数表并缓存 $2^k-1$ 集合。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cmath>
#include <iostream>
// 判断 target 能否被“纯物理攻击”恰好耗尽
// 物理攻击第 i 次伤害为 2^(i-1)，累加和为 2^i - 1
// 返回所需攻击次数；若无法恰好耗尽则返回 -1
int is_equal_sum(int target) {
int tmp_sum = 0;
for (int j = 0; j < 31; j++) {
tmp_sum += std::pow(2, j); // 累加 2^0 + 2^1 + ... + 2^j
if (tmp_sum == target) {
return j + 1; // 恰好耗尽，返回攻击次数
}
if (tmp_sum > target) {
return -1; // 已超过，后续更大，直接失败
}
}
return -1; // 31 次内仍无法满足
}
// 朴素判断 n 是否为质数
bool is_prime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= std::sqrt(n); i++) {
if (n % i == 0) {
return false; // 出现因子，非质数
}
}
return true; // 无因子，质数
}
int main() {
int t;
std::cin >> t; // 读入测试组数
for (int i = 0; i < t; i++) {
int h;
std::cin >> h; // 当前怪物血量
// 先尝试“纯物理攻击”能否恰好击败
int count = is_equal_sum(h);
// 再尝试“使用一次魔法攻击”的情况：枚举魔法伤害质数 x
// 从大到小枚举，可更快找到最小总次数（贪心思想）
for (int j = h; j >= 2; j--) {
if (is_prime(j)) { // j 是质数，可作为魔法伤害
int target = h - j; // 剩余需用物理攻击补足的血量
if (target == 0) {
count = 1; // 仅一次魔法攻击即可
break;
}
int tmp_count = is_equal_sum(target);
if (tmp_count != -1) { // 剩余血量可被物理攻击恰好耗尽
int total = tmp_count + 1; // 总次数 = 物理次数 + 1 次魔法
if (count == -1 || total < count) {
count = total; // 更新最小次数
}
// 由于从大到小枚举，首次合法即最优，可提前退出
break;
}
}
}
std::cout << count << std::endl;
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
