解题思路
没什么好说的，就是打表找规律……
不难发现，三元组中第一个数的最后两位按照 \(00\to 01\to 10\to 11\) 的顺序变化，其他位也一样，同样，第二个数和第三个数中每两位分别按照 \(00\to 10\to 11\to 01\) 和 \(00 \to 11\to 01\to 10\) 的顺序变化，且与第一个数对应变化。那么只要我们第一个数确定了，第二个和第三个数也就确定了，因此，我们的问题变为了如何快速确定第一个数。
观察发现，当 \(n=4^k\) 且 \(k\in \mathbb Z\) 时，三元组第一个数为 \(n\)。并且可以看出，在第一个数为 \(4^k\sim 2^{2\times k}-1\) 的连续若干个三元组中，第一个数是连续的，即分别为 \(4^k,\dots,2^{2\times k}-1\)。由此，我们可以找到第一个小于等于 \(n\) 的 \(x\) 使得 \(x=4^k\) 且 \(k\in\mathbb Z\)，那么 \(n\) 所在三元组的第一个数即为 \(\displaystyle 2^k+\frac{n-2^k}{3}\)。
综上，本题步骤为：
- 找到第 \(n\) 个数所在三元组的第一个数；
- 令第一个数为 \(m\)，我们将 \(m\) 转化为二进制，并将其位数补为偶数；
- 根据 \(m\) 从最高位开始，每两位为一组，计算出对应的第 \(2\)、\(3\) 个数的这两位；
- 将第 \(2\)、\(3\) 个数转化位十进制下整数；
- 判断 \(M=n\bmod 3\) 并输出，若 \(M=1\)，输出第一个数，若 \(m=2\)，输出第二个数，否则输出第三个数。
AC 代码
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include <string.h>
#define int long long
#define N 100
int n,m;char a[N],b[N],c[N];
inline int GetStr(int x,char *s){
int ce=0;while(x){
s[++ce]='0'+(x&1);
x>>=1;
}return ce&1?ce+1:ce;
}
inline void GetNum(int &x,char *s,int len){
x=0;for(register int i=len;i>=1;--i)
x=(x<<1ll)+(s[i]-'0');
}
inline void work(){
scanf("%lld",&n);int lin;
for(register int i=60ll;i>=0ll;--i)
if((n>>i)&1ll){
m=i&1ll?i-1ll:i;
lin=m;break;
}
int sub=(1ll<<m),res=(n-sub)/3ll;
m=sub+res;int _1=m,_2,_3;
for(register int i=1;i<=80;++i)
a[i]='0';int ce=GetStr(m,a);
for(register int i=ce;i>=1;i-=2){
if(a[i]=='0'&&a[i-1]=='0'){
b[i]='0',b[i-1]='0';
c[i]='0',c[i-1]='0';
}else if(a[i]=='0'&&a[i-1]=='1'){
b[i]='1',b[i-1]='0';
c[i]='1',c[i-1]='1';
}else if(a[i]=='1'&&a[i-1]=='0'){
b[i]='1',b[i-1]='1';
c[i]='0',c[i-1]='1';
}else if(a[i]=='1'&&a[i-1]=='1'){
b[i]='0',b[i-1]='1';
c[i]='1',c[i-1]='0';
}
}GetNum(_2,b,ce),GetNum(_3,c,ce);
if(n%3==0) printf("%lld\n",_3);
else if(n%3==1) printf("%lld\n",_1);
else printf("%lld\n",_2);
}
signed main(){
int T;scanf("%lld",&T);
while(T--) work();
system("pause");
}