一道挺有意思的位运算的题。
\(\gcd(a,b)\) 与 \(a\oplus b\) 本来是没有什么联系的，也不好直接转化。
那么就需要一个中间数进行转化，一般来说会是一个临界值，否则不好找答案。
先观察 \(\gcd(a,b),a\leqslant b\)，可得 \(\gcd(a, b) = \gcd(b, a - b)\leqslant a - b\)。
然后观察 \(a\oplus b\)，由异或的性质易得 \(a - b\leqslant a\oplus b\leqslant a + b\)。
故当 \(\gcd(a, b) = a\oplus b\) 时，\(\gcd(a, b) = a\oplus b = a - b\)。
我们可以提前预处理，先枚举 \(\gcd(a, b)\)，然后枚举 \(a - b\) 就可以了。
令 \(V=\max\{a\}\)，则时间复杂度为 \(\mathcal{O}(V\log V + T)\)。
代码：
const int N = 3e7 + 5;
int n;
int f[N];
void init() {
for (int i = 1; i < N / 2; i++)
for (int j = i * 2; j < N; j += i) {
int k = j - i;
if ((j ^ k) == i) f[j]++;
}
for (int i = 1; i < N; i++) f[i] += f[i - 1];
}
int main() {
init();
int T = read();
for (int i = 1; i <= T; i++) {
n = read();
printf("Case %d: %d\n", i, f[n]);
}
return 0;
}