题解 | 最通俗易懂，最详细的题解

思路：看一眼数据，回答最多，但很显然这题要求我们用，也就是推一个式子。

由于必须O(1)回答，所以对于1到j的最短路径，一定是直接边

结论1：两个不同的正整数异或结果一定非负，既。

已知可以让原本偶数+1，奇数-1,

假设有中间转点k，则其路径至少是

。

若，也就是至少 ，容易发现无论j是奇数还是偶数，都不比这个方案数劣。

若 ，根据异或结果不小于差值可以证明，这里不展开

现在分析结果的输出，由于，所以结果是

考虑n是奇数的情况

除了1每一项都有个1跟他异或，所以有偶数个1，由于结合律和分配率，我们可以把偶数个1先进行异或，由于自己和自己异或一定得0，而0和任何数异或都得任何数，所以最终就变成

若x是奇数，则x和x-1异或一定为1（因为x和x-1只在末尾有不同，一个是0，一个是1），这n-1个数如果划分为2组

假设可以划分成偶数个组，形如

同理，如果可以划分为奇数个组，最后就是0异或上1，变成1，形如

考虑n是偶数的情况：

若n是偶数，则有奇数个1，把偶数个1先合并为0，只剩下一个1，最后形如

这一特殊形式肯定有公式，但如果考场上遇到了不会做没关系，可以试着推一推，还是想刚才那样。

如果把一个奇数和比他小1的数进行每2个每2个的分，既n-2肯定是偶数，然后还是像刚刚奇数那样分析，如果n-2进行2个2个的划分，如果分出偶数组，也就是(n-2)/2也是偶数，那么恰好是这样的一个情况

既(n-2)%2==0时，输出n+1，反之，如果是奇数组，会出现

因此我们的策略是：

当n是奇数时，把偶数个1全部小曲，此时剩下2到n这n-1个数，进行分组，若能分为奇数组，则为1，若能分为偶数组，则为0

当n是偶数时，此时计算1异或到n，若1和n之间能划分为奇数组，则为n，否则为n+1

如此，我们就完成了这道题，这道题如果不知道结论，利用异或的几个重要性质可以很快推出来，当然开头的证明大部分是猜的，因为O(1)的回答不可能允许我们再去找任何最短路，唯一的可能就是1到j的最短路就是1异或上j

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false),cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        if(n&1){
            n--;
            n/=2;
            if(n&1)cout<<1;
            else cout<<0;
        }
        else{
            int t=n;
            n-=2;
            n/=2;
            if(n&1)cout<<t;
            else cout<<t+1;
        }
        
        cout<<"\n";
    }
}
// 64 位输出请用 printf("%lld")