自动搬运

查看原文

来自洛谷，原作者为

	yuruilin2026 「形骸的残响に绊され灭びゆく都市を」|| INFP-T

搬运于2025-08-24 21:16:45，当前版本为作者最后更新于2024-11-09 08:43:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道更水的黄题。
同机房的大佬 Hootime 如此说道。
那么话不多说，上思路。
对于每一个怪物，我们假设小杨会先使用物理攻击，再使用魔法攻击。

Q：为什么呢？
A：为什么？难道先用魔法攻击再用物理攻击造成的伤害不是一样的吗？

因为要求最小的攻击次数，所以我们选择的质数应该尽量的大。
当物理攻击到 $i$ 次的时候，剩下的血量是一个质数，那就可以直接结束游戏了。
因为越早的物理攻击伤害越低，那么剩下的质数就应该是最大的了。
那么，上代码：

#include <bits/stdc++.h>
using namespace std;
int t,h;//样例数 
bool prime(int x){
	//判断质数的函数
	//有一个小优化(蒟蒻没学到数学必修一,不会证)
	//所有的大于5的质数都可以写成(6n+1)和(6n-1)的形式
	//写正常的判断质数的函数就可以了
    int fx[2] = {2,4};
	if(x == 1 || x == 4){
		return 0;
	}
	if(x == 2 || x == 3){
		return 1;
	}
	if(x % 2 == 0){
		return 0;
	}
	if(x % 3 == 0){
		return 0;
	}
	for(int i = 5,p = 0;i * i <= x;i+=fx[p],p=!p){
		if(x % i == 0) return 0;
	}
	return 1;
}
int main(){
	cin.tie(0);//cin加速 
	cin >> t;
	while(t--){
		int l = 1,i = 0;//这次物理攻击的伤害,轮数 
		cin >> h;
		while(h > 0){
			if(prime(h)){//如果剩下的血量是质数 
				cout << i+1 << endl;//+1是因为要再攻击一次 
				break;
			}
			h -= l;//减少血量 
			i++;//增加轮数 
			l *= 2;//增加伤害 
		}
		if(prime(h)){//如果剩下的血量是质数(刚刚输出过了)
			continue;
		}
		else if(h < 0){//小于0,说明不能击败怪物(能击败早就击败了)
			cout << -1 << endl;
		}
		else{//特判只用物理攻击就可以的情况 
			cout << i << endl;
		}
	}
	return 0;
}