GCD XOR UVA 12716 找规律 给定一个n，找多少对(a,b)满足1<=b<=a<=n,gcd(a,b)=a^b；

/**
题目：GCD XOR UVA 12716
链接：https://vjudge.net/problem/UVA-12716
题意:给定一个n，找多少对(a,b)满足1<=b<=a<=n,gcd(a,b)=a^b；
思路：
打表找规律发现：满足条件的结果一定满足，gcd(a,b) = a-b;

即：先确定每一个a以及它的约数c可以获得，b = a-c; 如果a^b=c 那么满足。

时间复杂度nlg(n)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 3e7+10;
const double eps = 1e-6;
ll f[maxn];
void init()
{
    memset(f, 0, sizeof f);
    for(int i = 1; i <= maxn/2; i++){
        for(int j = i*2; j < maxn; j+=i){
            int b = j-i;
            if((j^b)==i){
                f[j]++;
            }
        }
    }
    for(int i = 1; i < maxn; i++) f[i] += f[i-1];
}
int main()
{
    int n;
    int T, cas=1;
    init();
    cin>>T;
    while(T--){
        scanf("%d",&n);
        printf("Case %d: %lld
",cas++,f[n]);
    }
    return 0;
}