题目描述

Given an integer N, find how many pairs (A, B) are there such that: gcd(A, B) = A xor B where

1 ≤ B ≤ A ≤ N.

Here gcd(A, B) means the greatest common divisor of the numbers A and B. And A xor B is the

value of the bitwise xor operation on the binary representation of A and B.

input

The first line of the input contains an integer T (T ≤ 10000) denoting the >number of test cases. The

following T lines contain an integer N (1 ≤ N ≤ 30000000).

output

For each test case, print the case number first in the format, ‘Case X:’ (here, X is the serial of the

input) followed by a space and then the answer for that case. There is no new-line between cases.

Sample Input

2

7

20000000

Sample Output

Case 1: 4

Case 2: 34866117

题意：

多组数据输入，每组数据输入一个n，问在小于n的数字里面能找到多少对数满足gcd（a,b)==a^b(大于b)

解题思路：

根据异或的性质我们可以发现，a^gcd(a,b)=b;

而gcd(a,b)又是a的约数，所以我们可以枚举c，就可以像筛素数那样做，然后在暴力小数据打表的时候发现gcd(a,b)=a-b，证明详见紫书318页。所以我们在筛的时候就找a^(a-b)是否等于b就行

代码

#include 
    
     using namespace std;int gcd (int a,int b){    if(b==0)return a;    else return gcd(b,a%b);}int a[300000005];void init(){    a[1]=0;    a[2]=0;    for(int i=1;i<300000007;i++)    {        for(int j=i+i;j<30000007;j+=i)        {            int tmp = j-i;            if((j^tmp) == i)            {                a[j]++;            }        }        a[i]+=a[i-1];    }}int main(){   init();   int t;   cin>>t;   int flg=1;   while(t--)   {    int n;    cin>>n;    int ans=a[n];    cout<<"Case "<
     
      <<": "<
      
       <
      
     
    

总结：

要多去想规律，比如说看到异或就要想到：如果a^b=c那么a^c=b,然后还要结合打表。