数论+埃筛题解

这题最重要的就是要知道一个数n经过i轮减掉2的 i-1 次幂可以为0， n+1 必定是2的 i 次幂（例如数字3可被2次物理攻击解决掉，数字7被三次，及以后分别是2的2次幂，2的3次幂）这是一个数论知识，可自己证明。思路是通过枚举每一个质数进行一次魔法攻击后再对每一个数进行上述判断减后的数+1是否为2的次幂以下为代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>prime;
bool mark[N];
int cnt,ans;
//不停除二判断（1是2的0次幂，也算）
bool check(int x){
    x++;
    while(x){
        if(x%2==1 and x!=1){
            return false;
        }
        else{
            x/=2;
            cnt++;
        }
    }
    return true;
}
int main(){
    int t,h;
    cin>>t;
    //埃筛找质数
    for(int i=2;i<N;i++){
       if(!mark[i]){
           prime.push_back(i);
           for(int j=i;j<N-i;j+=i){
               mark[j]=1;
           }
       }
    }
    while(t--){
        ans=1e9;
        bool flag=1;
        cin>>h;
        for(int i=0;prime[i]<=h;i++){
            cnt=0;
            if(check(h-prime[i])){
                //cout<<h-prime[i]<<endl;
                flag=0;
                ans=min(cnt,ans);
            }
        }
//判断是否找到了
        if(flag)cout<<-1<<endl;
        else cout<<ans<<endl;
    }
    
    return 0;
}