Perfect Triples (Codeforces 1338C)
Tags: Math, divide and conquer

Consider the infinite sequence $$$s$$$ of positive integers, created by repeating the following steps:  Find the lexicographically smallest triple of positive integers $$$(a, b, c)$$$ such that   $$$a \oplus b \oplus c = 0$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.  $$$a$$$, $$$b$$$, $$$c$$$ are not in $$$s$$$.  Here triple of integers $$$(a_1, b_1, c_1)$$$ is considered to be lexicographically smaller than triple $$$(a_2, b_2, c_2)$$$ if sequence $$$[a_1, b_1, c_1]$$$ is lexicographically smaller than sequence $$$[a_2, b_2, c_2]$$$.  Append $$$a$$$, $$$b$$$, $$$c$$$ to $$$s$$$ in this order.  Go back to the first step. You have integer $$$n$$$. Find the $$$n$$$-th element of $$$s$$$.You have to answer $$$t$$$ independent test cases.A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ if in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.Each of the next $$$t$$$ lines contains a single integer $$$n$$$ ($$$1\le n \le 10^{16}$$$) — the position of the element you want to know.

Output: In each of the $$$t$$$ lines, output the answer to the corresponding test case.

Note: The first elements of $$$s$$$ are $$$1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $$$

Sample Inputs:
9
1
2
3
4
5
6
7
8
9

Sample Outputs:
1
2
3
4
8
12
5
10
15

Solution (Python):
import sys
input = sys.stdin.readline
import bisect
L = [4 ** i for i in range(30)]

def calc(x):
    fami = bisect.bisect_right(L, x) - 1
    base = (x - L[fami]) // 3
    cl = x % 3
    if cl == 1:
        return L[fami] + base
    else:
        cl1 = L[fami] + base
        ANS = 0
        for i in range(30):
            x = cl1 // L[i] % 4
            if x == 1:
                ANS += 2 * L[i]
            elif x == 2:
                ANS += 3 * L[i]
            elif x == 3:
                ANS += L[i]
        if cl == 2:
            return ANS
        else:
            return ANS ^ cl1
t = int(input())
for tests in range(t):
    print(calc(int(input())))

Solution (Python):
T = int(input())
f = [0, 1, 2, 3, 4, 8, 12, 5, 10, 15, 6, 11, 13, 7, 9, 14]
ff = [0, 2, 3, 1]
for _ in range(T):
    n = int(input())
    if n <= 15:
        print(f[n])
        continue
    temp = n
    now = 0
    while temp:
        temp //= 4
        now += 1
    temp = (n + 2) // 3
    lastAns = (1 << 2 * (now - 1)) + (n - (1 << 2 * (now - 1))) // 3
    if n % 3 == 1:
        print(lastAns)
    else:
        sx = (n - (1 << 2 * (now - 1))) // 3
        temp = 1 << 2 * now - 1
        ii = 1
        while sx:
            temp += ii * ff[sx % 4]
            sx //= 4
            ii *= 4
        if n % 3 == 2:
            print(temp)
        else:
            print(lastAns ^ temp)

Solution (Python):
import bisect
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
pow4 = [1]
s = [0]
for _ in range(30):
    s.append(s[-1] + pow4[-1])
    pow4.append(4 * pow4[-1])
z = [0, 2, 3, 1]
for _ in range(t):
    n = int(input())
    n -= 1
    x = n // 3
    i = bisect.bisect_right(s, x) - 1
    y = x - s[i]
    a = pow4[i] + y
    b = 2 * pow4[i]
    for j in range(i):
        b += pow4[j] * z[y % 4]
        y >>= 2
    c = a ^ b
    ans0 = [a, b, c][n % 3]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))