题意： 问 gcd(i,j) = i ^ j  的对数（j <=i <= N ） N的范围为30000000，有10000组例子

思路：GCD(a,b) = a^b = c

GCD(a/c,b/c) = 1 (1)

(a-b) <= c (2)

(a/c-b/c) <=1 (3)

(1)(3) => a/c-b/c = 1=> a-b=c

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#include <cmath>

using namespace std;

const int maxn = 30000000+10;

typedef long long LL;

int N;

int ret[maxn];

void init() {

    for(int i = 3; i < maxn; i+=2) ret[i] = 1;

    for(int i = 2; i < maxn/2; i++) {

        for(int j = i+i; j < maxn; j += i) {

            int k = j-i;

            if( (k^j) == i){

                ret[j]++;

            }

        }

    }

    for(int i = 1; i < maxn; i++) ret[i] += ret[i-1];

}

int main(){

    int ncase,T=1;

    init();

    cin >> ncase;

    while(ncase--) {

        scanf("%d",&N);

        printf("Case %d: %d\n",T++,ret[N]);

    }

    return 0;

}