G5009 [GESP202409 五级] 挑战怪物 题解

知识点：素数筛、枚举、数学建模。

解题思路

枚举物理攻击次数i，累计伤害为2^i-1。若恰等于h，可不用魔法；若剩余正血量为质数，可补一次魔法，取总次数最小值。

为什么正确

i次物理攻击的总伤害固定，至多一次魔法使其他可行方案只取决于剩余是否为质数，枚举i覆盖全部组合。

易错点

剩余为0时不能再补魔法；剩余为1也不是质数；必须恰好消灭怪物，不能过量伤害。

复杂度

预筛M后，每组O(log h)，空间O(M)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int>p(100001,1);
    p[0]=p[1]=0;
    for(int i=2;i*i<=100000;i++)if(p[i])for(int j=i*i;j<=100000;j+=i)p[j]=0;
    int t,h;
    cin>>t;
    while(t--) {
        cin>>h;
        int ans=100;
        for(int i=0;i<=16;i++) {
            int s=(1<<i)-1;
            if(s==h)ans=min(ans,i);
            if(h>s&&p[h-s])ans=min(ans,i+1);
        }
        cout<<(ans==100?-1:ans)<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。