AcWing 631. Googol字符串 (递归、思维题）

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,k,res;
void dfs(int k,int p,int cnt){
    if(k==(p+1)/2){
        res=0;
        for(int i=0;i<cnt;i++){
            res^=1;
        }
        return;
    }
    if(k<(p+1)/2){
        dfs(k,p/2,cnt);
    }
    else{
        int tep=p/2+1-(k-p/2-1);
        //cout<<tep<<" "<<p/2<<endl;
        dfs(tep,p/2,cnt+1);
    
    }
    
}
signed main(){
    cin>>t;
    for(int _=1;_<=t;_++){
        cin>>k;
        int p=1;
        while(p<k){
            p*=2;
            p++;
        }
        //cout<<p<<endl;
        dfs(k,p,0);
        printf("Case #%lld: %lld\n",_,res);
        
    }
}