挑战怪物

题目描述

⼩杨正在和⼀个怪物战⽃，怪物的⾎量为 ，只有当怪物的⾎量恰好为 时⼩杨才能够成功击败怪物。 ⼩杨有两种攻击怪物的⽅式： 物理攻击。假设当前为⼩杨第 次使⽤物理攻击，则会对怪物造成 点伤害。 魔法攻击。⼩杨选择任意⼀个质数 （ 不能超过怪物当前⾎量），对怪物造成 点伤害。由于⼩杨并不擅长魔 法，他只能使⽤⾄多⼀次魔法攻击。 ⼩杨想知道⾃⼰能否击败怪物，如果能，⼩杨想知道⾃⼰最少需要多少次攻击。

输入格式

第⼀⾏包含⼀个正整数 ，代表测试⽤例组数。 接下来是 组测试⽤例。对于每组测试⽤例，第⼀⾏包含⼀个正整数 ，代表怪物⾎量。

输出格式

对于每组测试⽤例，如果⼩杨能够击败怪物，输出⼀个整数，代表⼩杨需要的最少攻击次数，如果不能击败怪物， 输出 。 3.2.4 样例1 1 3 2 6 3 188 4 9999 1 2 2 4 3 -1 对于第⼀组测试⽤例，⼀种可能的最优⽅案为，⼩杨先对怪物使⽤魔法攻击，选择质数 造成 点伤害，之后对怪 物使⽤第 次物理攻击，造成 点伤害，怪物⾎量恰好为 ，⼩杨成功击败怪物。 子任务编号 数据点占比 1 20% 2 20% 3 60% 对于全部数据，保证有 。 3.2.5 参考程序 1 #include <bits/stdc++.h> 2 using namespace std; 3 vector prime; 4 bool is_prime[100010]; 5 void Eratosthenes(int n) { 6 is_prime[0] = is_prime[1] = false; 7 for (int i = 2; i <= n; ++i) is_prime[i] = true; 8 for (int i = 2; i <= n; ++i) { 9 if (is_prime[i]) { 10 prime.push_back(i); 11 if ((long long)i * i > n) continue; 12 for (int j = i * i; j <= n; j += i) 13 is_prime[j] = false; 14 } 15 } 16 } 17 int main() { 18 Eratosthenes(100000); 19 int t; 20 cin>>t; 21 while(t--){ 22 int tmp=1; 23 int x; 24 cin>>x; 25 int ans=0; 26 while(1){ 27 if(is_prime[x]){ 28 ans++; 29 break; 30 } 31 x-=tmp; 32 ans++; 33 if(x<=0){ 34 if(x<0)ans=-1; 35 break; 36 } 37 tmp*=2; 38 } 39 cout<<ans<<"\n"; 40 } 41 }

样例输入 #1

1 3
2 6
3 188
4 9999
1 2
2 4
3 -1
对于第⼀组测试⽤例，⼀种可能的最优⽅案为，⼩杨先对怪物使⽤魔法攻击，选择质数 造成 点伤害，之后对怪
物使⽤第 次物理攻击，造成 点伤害，怪物⾎量恰好为 ，⼩杨成功击败怪物。
子任务编号 数据点占比
1 20%
2 20%
3 60%

样例输出 #1

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。