题意:输入整数n,(1<= n <= 30000000),有多少队整数(a, b)满足: 1<=b<=a<=n,且gcd(a, b) = a XOR b。例如 n = 7时,有4对:(3, 2), (5, 4), (6, 4), (7, 6)。
分析:本题看上去难得找到一个计算公式,因为gcd和xor毫无关系。不过xor的好处是 a xor b = c 则 a xor c = b,所以我们可以枚举a, c,然后计算b = a xor c,最后验证一下是否有 gcd(a, b) = c, 时间复杂度如何?因为c 是 a的约数,所以枚举的复杂度为n*logn,再加gcd的复杂度,这个算法的复杂度为O(n*logn*logn),显然是不能通过此题的。但是我们先把这个程序写出来之后,打印一些满足 gcd(a, b) = a xor b = c的三元组(a, b, c),容易发现一个规律 c = a - b。
证明如下:不难发现a - b <= a xor b, 且 a - b >=c。假设存在 c 使得 a - b > c,则 c < a-b <= a xor b, 与c = a xor b矛盾。
有了这个结论,我们直接枚举a, c,直接计算 b = a - c, 则gcd(a, b) = gcd(a, a - c) = c, 所以只需要变成验证 c = a xor b即可。
复杂度降为 O(n * logn),可以通过此题

代码如下:

//
//Created by BLUEBUFF 2016/1/11
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
//#include <bits/stdc++.h>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 30000010;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
const double PI = acos(-1);
//head


int sum[30000010];
void pre_init(){
    for(int c = 1; c < maxn/ 2; c++){
        for(int a = c + c; a < maxn; a += c){
            int b = a - c;
            if((a ^ b) == c) sum[a]++;
        }
    }
    for(int i = 2; i < maxn; i++){
        sum[i] += sum[i - 1];
    }
}
int main()
{
    pre_init();
    int T, n, ks = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        printf("Case %d: %d\n", ++ks, sum[n]);
    }
    return 0;
}