欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目描述】
小杨正在和一个怪物战斗，怪物的血量为h hh，只有当怪物的血量恰好为0 00时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式：
- 物理攻击。假设当前为小杨第i ii次使用物理攻击，则会对怪物造成2 i − 1 2^{i-1}2i−1点伤害。
- 魔法攻击。小杨选择任意一个质数x xx（x xx不能超过怪物当前血量），对怪物造成x xx点伤害。由于小杨并不擅长魔法，他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。
【输入】
第一行包含一个正整数t tt，代表测试用例组数。
接下来是t tt组测试用例。对于每组测试用例，第一行包含一个正整数h hh，代表怪物血量。
【输出】
对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物，输出− 1 -1−1。
【输入样例】
3 6 188 9999【输出样例】
2 4 -1【代码详解】
《洛谷 B4050 挑战怪物》 #贪心# #数论# #GESP# #2024#
#include<bits/stdc++.h>usingnamespacestd;vector<int>prime;// 用于存储所有素数boolis_prime[100010];// 标记数组，用于判断一个数是否为素数// 埃氏筛法，生成从2到n的所有素数voidEratosthenes(intn){memset(is_prime,true,sizeof(is_prime));// 初始化标记数组，全设为true（假定全是素数）is_prime[0]=is_prime[1]=false;// 0和1不是素数for(inti=2;i<=n;i++){if(is_prime[i]){// 如果当前数字是素数prime.push_back(i);// 将其加入素数列表for(intj=2*i;j<=n;j+=i)// 将该素数的倍数全部标记为非素数is_prime[j]=false;}}}intmain(){Eratosthenes(100000);// 生成最多到100000的所有素数intt;// 测试用例数量cin>>t;while(t--){inttmp=1;// 初始攻击力intx;// 怪物的血量cin>>x;intans=0;// 攻击次数while(true){if(is_prime[x]){// 如果当前血量是素数ans++;// 增加一次攻击break;// 结束循环}x-=tmp;// 使用物理攻击，减少血量ans++;// 增加一次攻击次数if(x<=0){// 如果血量小于等于0if(x<0)ans=-1;// 如果血量小于0，设置结果为-1表示失败break;// 结束循环}tmp*=2;// 每次攻击后，攻击力翻倍}cout<<ans<<endl;// 输出结果}return0;}【运行结果】
3 6 2 188 4 9999 -1
