链接：

 

题意：

输入整数n（1≤n≤30000000），有多少对整数(a,b)满足：1≤b≤a≤n，且gcd(a,b)=a xor b。

例如n=7时，有4对：(3,2), (5,4), (6,4), (7,6)。

 

分析：

若a xor b = c，则a xor c = b，所以可以枚举a和c，然后算出b=a xor c，最后验证一下是否有gcd(a,b)=c。

时间复杂度如何？因为c是a的约数，所以和素数筛法类似，时间复杂度为n/1+n/2+…+n/n=O(nlogn)。

再加上gcd的时间复杂度为O(logn)，所以总的时间复杂度为O(n(logn)(logn))。

上述程序写出来之后，可以打印一些满足gcd(a,b)=a xor b=c的三元组(a,b,c)，然后很容易发现：c=a-b。

有了这个结论，还是沿用上述算法，枚举a和c，计算b=a-c，则gcd(a,b)=gcd(a,a-c)=c，

因此只需验证是否有c = a xor b，时间复杂度降为了O(nlogn)。

c=a-b的证明如下（其中⊕代表异或）：

① c=a⊕b

② a-b≤a⊕b

③ a-b≥c

由①②③得：a-b≥c且a-b≤c，所以a-b=c。

证明②：

证明③：

因为c=gcd(a,b)且a>b，所以a/c-b/c≥1，即a-b≥c，证毕。

 

代码：

1 import java.io.*; 2 import java.util.*; 3  4 public class Main { 5     static final int UP = 30000000 + 1; 6     static int sum[] = new int[UP]; 7      8     static void constant() { 9         for(int c = 1; c < UP; c++) {10             for(int a = c + c; a < UP; a += c) {11                 int b = a - c;12                 if((a ^ b) == c) sum[a]++;13             }14         }15         for(int i = 1; i < UP; i++) sum[i] += sum[i-1];16     }17     18     public static void main(String args[]) {19         Scanner cin = new Scanner(new BufferedInputStream(System.in));20         constant();21         22         int T = cin.nextInt();23         for(int cases = 1; cases <= T; cases++) {24             int n = cin.nextInt();25             System.out.printf("Case %d: %d\n", cases, sum[n]);26         }27         cin.close();28     }29 }