1秒题解

先写判定质数的函数，再挨个写每种情况

//版权所有，侵权必究 
#include<bits/stdc++.h>
using namespace std;

bool isprime(long long x){
    if(x < 2) return false;
    for(long long i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}

int a[1000010];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        long long x;
        cin>>x;

        long long ans = LLONG_MAX;

        // k=0，0次物理，只用魔法
        if(isprime(x))
        {
            ans = 1;
        }

        //情况1：不用魔法，全部物理 h = 2^k - 1 ，k>=1
        for(int k=1;k<=60;k++)
        {
            long long sum = (1LL << k) - 1;
            if(sum == x)
            {
                ans = min(ans,(long long)k);
                break;
            }
            if(sum > x) break;
        }

        //情况2：用1次魔法，h = p + sum  → p = x?sum ，k>=1次物理
        for(int k=1;k<=60;k++)
        {
            long long sum = (1LL << k) - 1;
            long long p = x - sum;
            if(p>0 && isprime(p))
            {
                long long step = k + 1;
                if(step < ans) ans = step;
            }
        }

        if(ans == LLONG_MAX){
            cout<<"-1"<<endl;
        }else{
            cout<<ans<<endl;
        }
    }
    return 0;
}