UVALive-6657-GCD XOR - c++编程基础

Given an integer N, nd 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 rst 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 rst 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.

Explanation

Sample 1: For N = 7, there are four valid pairs: (3, 2), (5, 4), (6, 4) and (7, 6).

Sample Input
2
7
20000000

Sample Output
Case 1: 4

Case 2: 34866117

思路：相差为两个i以上的两个i的倍数异或值不可能等于i，可以自己推一下。有了这个结论就好办了，直接枚举最大公约数即可。

#include 
  
   

int d[30000001];

int main()
{
    int T,i,j,n=30000000;

    for(i=1;i<=n;i++) for(j=i+i+i;j<=n;j+=i) if((j^(j-i))==i) d[j]++;//相差为两个i以上的两个i的倍数异或不可能等于i

    for(i=1;i<=n;i++) d[i]+=d[i-1];

    scanf("%d",&T);

    for(i=1;i<=T;i++)
    {
        scanf("%d",&n);

        printf("Case %d: %d\n",i,d[n]);
    }
}