题解 | 小苯的最短路

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
ll n;
ll pw2[50];

void solve()
{
    cin>>n;
    if(n==1)cout<<0<<'\n';
    else 
    {
        ll ans = 0;
        if((n/2)%2==1)ans^=1;
        for(int i=1;i<=31;i++)
        {
            if((n+1)%pw2[i+1]<=pw2[i])continue;
            else
            {
                ll cur =  (n+1)%pw2[i+1]-pw2[i];
                if(cur%2==1)ans^=(1<<i);
            }
        }
        // ans^=1;
        cout<<ans<<'\n';
    }

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pw2[0]=1;
    for(int i=1;i<=40;i++)pw2[i]=pw2[i-1]*2;
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();

    }


    return 0;
}