题解：B4050 [GESP202409 五级] 挑战怪物
niuniudundun
·
·
题解
原题
B4050
题目大意
一个数 h 每次操作有对 h 进行减去 2^{i-1} 或减去一个质数，为 0 停止，求操作次数。
解法
step1. 如果 h 是质数，则直接输出 ans （操作次数）。
step2. 如果不是减去 2^{i-1} ，并且 ans\longrightarrow ans+1。
step3. 如果 h 小于 0 ，说明不可击败怪物。
step4. 如果 h 等于 0 ，输出 ans 。
step5.重复步骤。
问题
魔法攻击
题目中说：
至多一次魔法攻击。
众所周知质数均为奇数（这里不讨论 2 ），有两种情况：
但是在程序中，如果 $h$ 已经是质数那么会被魔法攻击变成 $0$ ； $h$ 不是质数，那么**一定**会被 $2^0$ 变为偶数。
$h$ 为偶数，答案为奇数，减完后一定会被 $2^{0}$ 再变为偶数，然后在后面操作中会被物理攻击（减去 $2^{i-1}$ ）中变成 $0$。
但是在程序中， $h$ 会被物理攻击（减去 $2^{i-1}$ ），变为 $2$ 或 $0$ 。如果结果 $h$ 为 $2$ ，也会被魔法攻击变成 $0$。
如果 $h$ 为 $2$ ，也会被魔法攻击变成 $0$。
所以只能进行一次魔法攻击（减去质数）。
# 代码
```cpp
#include<iostream>
using namespace std;
int t;
const int maxn=1e5+1;
bool prime[maxn];
int main(){
cin>>t;
for(int i=2;i<=maxn;i++){//处理质数
prime[i]=true;
}
for(int i=2;i<=maxn;i++){
if(prime[i]){
for(int j=i*2;j<=maxn;j+=i){
prime[j]=false;
}
}
}
for(int i=1;i<=t;i++){
int ans=0;
int h;
cin>>h;
for(int j=1;1;j*=2){//计算ans
if(prime[h]){//魔法攻击
ans++;
break;
}
h-=j;//物理攻击
ans++;
if(h<0){
ans=-1;
break;
}
if(h==0){
break;
}
}
cout<<ans<<endl;
}
return 0;
}
```
复杂度：$\Theta \left ( t\log_{2}{h} \right ) $。