题目回顾
小杨正在挑战一个血量为 h 的怪物，他有两种攻击方式：
物理攻击：第
i次使用造成2^(i-1)点伤害魔法攻击：选择任意质数
x造成伤害，最多使用一次
问：最少需要多少次攻击才能恰好击败怪物？若无法击败则输出 -1。
思路分析
核心观察
物理攻击的累加特性第1次物理：1点第2次物理：2点第3次物理：4点前
i次物理总伤害 =2^0 + 2^1 + ... + 2^(i-1) = 2^i - 1魔法攻击的灵活性魔法可以选择任意质数，且最多使用一次，这给了我们极大的调整空间。
问题转化问题等价于：是否存在
i次物理攻击（总伤害为2^i - 1），使得：要么
h - (2^i - 1) = 0（纯物理击败）要么
h - (2^i - 1)是质数（物理+魔法击败）
算法设计
由于数据范围 h ≤ 10^5，我们可以：
预处理：提前筛出
1~10^5内的所有质数预处理：提前计算所有可能的物理攻击总伤害
2^i - 1贪心枚举：从小到大枚举物理攻击次数，首次找到的解即为最优
代码实现与注解
#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 5;int f[N], p[N], cnt; // f标记合数，p存储质数int q[N], len; // q存储前i次物理攻击总伤害// 线性筛（欧拉筛）预处理质数void findP(int n) {f[0] = f[1] = 1; // 0和1不是质数for (int i = 2; i <= n; i++) {if (!f[i]) p[++cnt] = i; // 存储质数for (int j = 1; j <= cnt && i * p[j] <= n; j++) {f[i * p[j]] = 1; // 标记合数if (i % p[j] == 0) break; // 保证每个合数只被最小质因子筛掉}}}// 预处理物理攻击累加伤害void fingM(int n) {for (int i = 1; (1 << i) - 1 <= n; i++) {q[++len] = (1 << i) - 1; // q[i]表示前i次物理总伤害}}// 求解最少攻击次数int deal(int h) {// 情况1：只用魔法攻击if (!f[h]) return 1;// 情况2：物理攻击 + 可能的魔法攻击for (int i = 1; q[i] <= h; i++) {int need = h - q[i]; // 物理攻击后剩余血量if (need == 0) return i; // 纯物理击败if (!f[need]) return i + 1; // 物理+魔法击败}return -1; // 无解}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// 预处理findP(100000);fingM(100000);int T, h;cin >> T;while (T--) {cin >> h;cout << deal(h) << endl;}return 0;}
关键点解析
1. 线性筛优化
if (i % p[j] == 0) break;这一行是线性筛的精髓，确保每个合数只被其最小质因子筛掉，时间复杂度降为 O(n)。
2. 位运算技巧
(1 << i) - 1 // 等价于 2^i - 1使用位运算计算2的幂次，效率更高、代码更简洁。
3. 贪心正确性证明
由于物理攻击次数 i 递增时，总伤害 q[i] 单调递增，剩余血量 need 单调递减。我们从小到大枚举，找到的第一个可行解就是最少攻击次数。
复杂度分析
预处理：
O(N)，其中N = 10^5单次查询：
O(log h)，因为q[i]呈指数增长总体复杂度：
O(N + T·log h)，完美通过所有测试点
易错点提醒
边界处理：注意
need = 0的情况要单独判断数组范围：确保质数表覆盖所有可能的
h值魔法限制：题目要求魔法至多使用一次，我们的枚举恰好符合这个限制
举一反三
这道题的核心思想可以迁移到很多场景：
预处理思想：当查询次数多、数据范围固定时，提前计算是优化利器
贪心策略：当状态空间具有单调性时，贪心往往能得到最优解
问题转化：将复杂约束转化为数学等式，简化问题模型
总结
"挑战怪物"作为GESP五级真题，考察了质数筛法、位运算、贪心算法等多个知识点。通过预处理将在线查询转化为离线计算，体现了"空间换时间"的经典优化思想。
