题目解析

我们有一个整数 $x$（$1 \le x \le 10^6$）和一个很大的整数 $m$（$1 \le m \le 10^{18}$）。需要统计满足以下条件的 $y$（$1 \le y \le m$）的个数：

1. $x \ne y$
2. $x \oplus y$ 是 $x$ 或 $y$ 的除数

关键观察

观察 $1$

由于 $x > 0$ 且 $y > 0$，$x \oplus y$ 不可能等于 $x$ 或 $y$（因为异或运算只有当另一个数为 $0$ 时才可能相等，而 $y \ge 1$）。

观察 $2$

如果 $d$ 是 $p$ 的一个除数且 $d < p$，那么 $d \le \lfloor \frac{p}{2} \rfloor$。
这意味着除数最多是原数的一半。

观察 $3$（核心结论）

如果 $y \ge 2x$，那么 $x \oplus y$ 不可能成为 $x$ 或 $y$ 的除数。

证明：

• 首先，当 $y \ge 2x$ 时，$y$ 的最高二进制位一定高于 $x$ 的最高二进制位。
  因此，$x \oplus y$ 的最高位与 $y$ 相同，所以 $x \oplus y \ge 2^{\lfloor \log_2 y \rfloor} > \frac{y}{2}$。

• 若 $x \oplus y$ 是 $y$ 的除数，则必须满足 $x \oplus y \le \frac{y}{2}$（因为除数小于 $y$ 时最多为 $y/2$）。
  但我们已经得到 $x \oplus y > \frac{y}{2}$，矛盾。所以 $x \oplus y$ 不能是 $y$ 的除数。

• 同理，$x \oplus y$ 的最高位也高于 $x$ 的最高位，所以 $x \oplus y > x$。
  若 $x \oplus y$ 是 $x$ 的除数，则必须满足 $x \oplus y \le \frac{x}{2}$（因为除数小于 $x$ 时最多为 $x/2$），但这与 $x \oplus y > x$ 矛盾。
  所以 $x \oplus y$ 也不能是 $x$ 的除数。

因此，当 $y \ge 2x$ 时，不存在满足条件的 $y$。

结论

我们只需要考虑 $y < 2x$ 的范围。
由于 $x \le 10^6$，$2x \le 2 \times 10^6$，这是一个可以枚举的范围。

算法步骤

对于每个测试用例：

$1$. 读入 $x$ 和 $m$。 $2$. 令 $limit = \min(2x, m)$，因为：

• 当 $y \ge 2x$ 时无解
• 同时 $y$ 不能超过 $m$ $3$. 枚举 $y = 1$ 到 $limit$：
• 如果 $x = y$，跳过
• 令 $d = x \oplus y$
• 如果 $d$ 能整除 $x$ 或能整除 $y$，则计数加 $1$ $4$. 输出计数

时间复杂度

每个测试用例枚举 $O(x)$ 个 $y$，所有测试用例的 $x$ 之和不超过 $10^7$，因此总复杂度为 $O(\sum x)$，在时限内可行。

代码实现

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
  int x; ll m; cin >> x >> m;

  int ans = 0;
  // 只需要枚举 y < 2x 且 y <= m 的范围
  for (int y = 1; y <= min(2LL * x, m); y++) {
    if (x != y) {
      int d = x ^ y;
      if (x % d == 0 || y % d == 0) {
        ++ans;
      }
    }
  }
  cout << ans << '\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

示例验证

以第一个测试用例 $x = 6, m = 9$ 为例：

• $2x = 12$，$limit = \min(12, 9) = 9$
• 枚举 $y = 1$ 到 $9$：

结果：$3$ 个有效值（$y = 4, 5, 7$），与题目输出一致。