GCD等于XOR
题目描述
输入格式
输出格式
题意翻译
输入数据组数t，接下来t行每行给定一个数字n，如样例所示格式输出满足1<=b<=a<=n且gcd(a,b)==a xor b的(a,b)二元组个数。
输入样例
2
7
20000000
输出样例
Case 1: 4
Case 2: 34866117
题意分析
这道题很良心，题目即做法
由题目我们可得出式子：
用程序实现：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
const int big=30000001;
int i,j,n,t,a[big];
cin>>t;
int tt=big>>1;
for(i=1;i<=tt;i++)
for(j=(i<<1);j<=big;j+=i)
if(j^i==j-i)
a[j]++;
for(i=2;i<=big;i++)
a[i]=a[i]+a[i-1];
for(i=1;i<=t;i++)
{
cin>>n;
cout<<"Case 1: "<<i<<endl;
cout<<"Case 2: "<<a[n];
}
return 0;
}