UVa 12716 GCD XOR

题目

题目大意

输入整数(n)((1 ≤ n ≤ 30000000)), 有多少对整数((a, b))满足: (1 ≤ b ≤ a ≤ n), 且((a, b) = a ⊕ b)(这里((a, b))表示(a)与(b)的最大公约数, (⊕)表示按位异或运算)。例如(n = 7)时, 有(4)对: ((3, 2)), ((5, 4)), ((6, 4)), ((7, 6))。

题解

由于最大公约数和按位异或看起来毫不相关, 可以先写个暴力程序打一些满足((a, b) = a ⊕ b = c)的表, 然后观察可以发现: (c = a - b)

证明如下: 刘汝佳说不难发现(a - b ≤ a ⊕ b), 且(a - b ≥ c)。假设存在(c)使得(a - b > c), 则(c < a - b ≤ a ⊕ b), 与(c = a ⊕ b)矛盾。

有了这个结论, 枚举(a)和(c), 计算(b = a - c), 则((a, b) = (a, a - c) = c), 此时就只需要验证(c = a ⊕ (a - c))了。

代码

#include <cstdio>
int form[30000010], T, n;
int main(int argc, char **argv) {
  for (register int c(1); c <= 15000000; ++c) {
    for (register int a(c << 1); a <= 30000000; a += c) {
      if ((a ^ (a - c)) == c) ++form[a];
    }
  }
  for (register int i(2); i <= 30000000; ++i) form[i] += form[i - 1];
  scanf("%d", &T);
  for (register int i(1); i <= T; ++i) {
    scanf("%d", &n);
    printf("Case %d: %d
", i, form[n]);
  }
  return 0;
}