1509.G.Triple Nim
Description

Alice and Bob are always playing all
kinds of Nim games and Alice always goes first. Here is the rule of Nim game: There are some distinct
heaps of stones. On each turn, two players should remove at least one stone
from just one heap. Two player will remove stone one after another. The player
who remove the last stone of the last heap will win.

Alice always wins and
Bob is very unhappy. So he decides to make a game which Alice will never win.
He begins a game called “Triple Nim”, which is the Nim game with three heaps of
stones. He’s good at Nim game but bad as math. With exactly N stones, how many
ways can he finish his target? Both Alice and Bob will play optimally.

Input

Multiple test cases. The first line
contains an integer T (T <= 100000), indicating the number of test
case. Each case contains one line, an integer N (3 <= N <=
1000000000) indicating the number of stones Bob have.

Output

One line per case. The number of ways
Bob can make Alice never win.

Sample Input

3
3
6
14

Sample Output

0
1
4

Hint

In the third case, Bob can make three heaps (1,6,7),
(2,5,7), (3,4,7) or (3,5,6).

玄学的一道题。
需要分成三个数，使三个数异或和为0
如果n为奇数，肯定不能分成 直接输出0
如果n为偶数，查找n的二进制表示中有多少个1，每一个1要在两个数里有，则每个1有3种选择。然后去掉全是0的情况，最后除以6（因为是3个数）来除去1 2 3，3 2 1，2 1 3，，，这种重复情况

#include <bits/stdc++.h>
using namespace std;
int main()
{
   
    int t;
    long long a[100005];
    a[1]=0;
    a[2]=1;
    for(int i=3;i<=100000;i++)
    {
   
        a[i]=a[i-1]*3+1;
    }
    scanf("%d",&t);
    while(t--)
    {
   
        long long b,m;
        scanf("%lld",&b);
        if(b%2)
            cout<<0<<'\n';
        else
        {
   
            m=0;
            while(b)
            {
   
                if(b&1)
                    m++;
                b>>=1;
            }
            cout<<a[m]<<'\n';
        }
    }
    return 0;
}