2024-09 · 5级 · 挑战怪物

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1184 字

CCF 原卷官方标程 · 数组与向量、质数、位运算、贪心 · 本地编译通过

2024-09
数组与向量

正文

// GESP 2024-09 C++ 5级 编程题 2 · 挑战怪物
// 原题：https://oj.yecheng.tv/p/gs2409l5p2
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1633836261703712.pdf
// 题意：小杨正在和一个怪物战斗，怪物的血量为 ，只有当怪物的血量恰好为时小杨才能够成功击败怪物。
// 知识点：数组与向量、质数、位运算、贪心
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 1/1 通过
//
#include <bits/stdc++.h>
using namespace std;
vector<int> prime;
bool is_prime[100010];
void Eratosthenes(int n) {
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) is_prime[i] = true;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            prime.push_back(i);
            if ((long long)i * i > n) continue;
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
}
int main() {
    Eratosthenes(100000);
    int t;
    cin>>t;
    while(t--){
        int tmp=1;
        int x;
        cin>>x;
        int ans=0;
        while(1){
            if(is_prime[x]){
                ans++;
                break;
            }
            x-=tmp;
            ans++;
            if(x<=0){
                if(x<0)ans=-1;
                break;
            }
            tmp*=2;
        }
        cout<<ans<<"\n";
    }
}

2024-09 · 5级 · 挑战怪物

正文

GESP 标程 · 考级真题的其它内容