异或

GitHub跳转原题关系图返回列表

由 gcd≤a-b≤a xor b 的夹逼得等号链 c=gcd=a-b=a xor b,于是枚举公约数 c 与其倍数 a,验证 b+c 相加不进位,O(n log n) 数完。

OJ: roj

题目 ID: 1801

难度:普及+/提高-

标签:数学数论位运算枚举python

创建: 2026-10-08 04:05

更新: 2026-10-08 04:05

形式化题目

给定正整数 nn,统计满足下式的无序数对 (a,b)(a, b) 的个数:

1⩽a,b⩽n,gcd⁡(a,b)=a⊕b. 1 \leqslant a, b \leqslant n, \qquad \gcd(a, b) = a \oplus b .

无序意味着 (a,b)(a,b) 与 (b,a)(b,a) 只算一次;由对称性我们约定 a>ba > b 来去重。

样例 n=3n = 3:候选对共 (32)=3\binom{3}{2} = 3 个,逐个验证

(a,b)(a,b) gcd⁡\gcd a⊕ba \oplus b 是否相等
(2,1)(2,1) 11 33 ×\times
(3,1)(3,1) 11 22 ×\times
(3,2)(3,2) 11 11 ✓\checkmark

只有 (2,3)(2,3) 满足,答案 11。

数据规模:30% 的测试点 n⩽1000n \leqslant 1000,60% 的 n⩽105n \leqslant 10^5, 100% 的 n⩽107n \leqslant 10^7。时限 1000 ms,空间 128 MB。

正解

思路

朴素做法。 对每对 (a,b)(a,b) 算一次 gcd⁡\gcd 和一次异或,n=107n = 10^7 时约有 5×10135 \times 10^{13} 个数对,不可能跑完。而答案本身只有 1.7×1071.7 \times 10^7 量级, 说明绝大多数数对都可以被一次性排除掉,不需要逐个检验。要找的就是这种"批量排除"的工具。

工具:一次夹逼。 设 a>ba > b,记 d=gcd⁡(a,b)d = \gcd(a,b)。两个方向的不等式同时收紧:

  1. 整除方向。 d∣ad \mid a 且 d∣bd \mid b,所以 d∣(a−b)d \mid (a-b),于是 d⩽a−bd \leqslant a-b。 (注意这是"约数不超过被它整除的数",等号当且仅当 a−b=da-b = d。)
  2. 异或方向。 对任意整数 a>ba > b,把 a−ba-b 与 a⊕ba \oplus b 按位看: 加法中 bb 的每一个 1 在 aa 中有对应位就产生进位,而进位只会被异或"抹掉", 抵消不了减法;可以证明 a⊕b⩾a−ba \oplus b \geqslant a - b。

把两个不等式拼在题目条件上:

a−b  ⩾  gcd⁡(a,b)  =  a⊕b  ⩾  a−b. a - b \;\geqslant\; \gcd(a,b) \;=\; a \oplus b \;\geqslant\; a - b .

夹逼迫使三处全部取等:

 gcd⁡(a,b)  =  a−b  =  a⊕b  =  c . \boxed{\ \gcd(a,b) \;=\; a - b \;=\; a \oplus b \;=\; c\ }.

这一条把"两个全局量相等"的判定,压缩成了"差与公约数相等"的差一判定: 原来要在所有数对里撒网,现在 cc 只能是 a−ba - b,即 cc 是 aa 的约数。

把等号链读成枚举方式。 记 c=a−bc = a-b。等号链说 c∣ac \mid a(因为 c=gcd⁡(a,b)c = \gcd(a,b) 整除 aa), 于是 aa 是 cc 的倍数,设 a=kca = kc(k⩾2k \geqslant 2,因为 b=(k−1)c⩾1b = (k-1)c \geqslant 1 要求 k⩾2k \geqslant 2), 相应地 b=a−c=(k−1)cb = a - c = (k-1)c。

反过来验证这个刻画是否"充要"。若 c∣ac \mid a 且 (a−c)&c=0(a-c) \& c = 0:

  • 第二式说明 (a−c)(a-c) 与 cc 的低位 1 不重叠,加法 b+cb + c 全程无进位, 故 a=b+ca = b + c 处 a⊕b=ca \oplus b = c;
  • 又 c∣ac \mid a 且 c∣bc \mid b,故 gcd⁡(a,b)⩾c\gcd(a,b) \geqslant c;而 gcd⁡(a,b)⩽a−b=c\gcd(a,b) \leqslant a-b = c, 所以 gcd⁡(a,b)=c\gcd(a,b) = c。

两边都是充要的,于是得到一条只需枚举一对 (c,a)(c, a) 就能判定的准则:

(c,a) 合法  ⟺  c∣a, a⩾2c, a⩽n, (a−c)&c=0. (c, a) \text{ 合法} \iff c \mid a,\ a \geqslant 2c,\ a \leqslant n,\ (a-c) \& c = 0 .

每个合法无序对 (a,b)(a,b) 唯一对应 c=gcd⁡(a,b)c = \gcd(a,b) 与 aa(bb 由 a−ca - c 唯一确定), 所以这样枚举不重不漏。

会不会重复计数? 不会。cc 是由数对本身决定的(c=a−bc = a-b),aa 也是; 反过来由 (c,a)(c, a) 唯一还原出 bb。不同的 (c,a)(c,a) 还原出的数对必然不同, 所以计数就是合法 (c,a)(c,a) 的个数。

为什么这样快。 枚举量是

∑c=1⌊n/2⌋⌊nc⌋−1  ≈  nln⁡n  ≈  1.53×108(n=107), \sum_{c=1}^{\lfloor n/2 \rfloor} \left\lfloor \frac{n}{c} \right\rfloor - 1 \;\approx\; n \ln n \;\approx\; 1.53 \times 10^8 \quad (n = 10^7),

比 5×10135 \times 10^{13} 小了五个数量级,n=107n = 10^7 下毫秒级可过。

以 c=1c = 1 为例,它覆盖 a=2,3,…,na = 2, 3, \dots, n,判定式退化为 (a−1)&1=0(a-1) \& 1 = 0, 即 a−1a - 1 为偶数、aa 为奇数——正好对上"奇数的 b=a−1b = a-1 一定是偶数"这类 c=1c = 1 的合法对。c=3c = 3 时只有满足 a≡0(mod3)a \equiv 0 \pmod 3 且 (a−3)&3=0(a-3) \& 3 = 0 的倍数入选,例如 a=6a = 6(b=3b = 3,3⊕6=5≠33 \oplus 6 = 5 \neq 3 被排除)、 a=9a = 9(b=6b = 6,6⊕9=156 \oplus 9 = 15,排除)……

实际入选的规模可以看真实数据:n=1000n = 1000 时答案 1580,n=105n = 10^5 时 173407, n=107n = 10^7 时 17440305——增长远慢于枚举量,说明绝大多数候选都在位运算那一步被筛掉, 这也印证了"批量排除"的直觉。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 04:05
# update_at: 2026-10-08 04:05

import sys


def count_pairs(n: int) -> int:
    """统计 [1,n] 内满足 gcd(a,b) = a xor b 的无序数对 (a,b) 个数。

    gcd(a,b) = a xor b 迫使 gcd(a,b) = a-b = a xor b = c(等号链),
    故只需枚举公约数 c 与它的倍数 a = b + c,再验证 b + c 相加不进位。
    """
    ans = 0
    # c 是较小的数 b,同时充当公约数:b = c, a = k*c(k >= 2)
    for c in range(1, n // 2 + 1):
        # (a - c) & c == 0 说明低位的 1 不重叠,即 a = (a-c) + c 不进位、异或等于 c
        ans += sum(1 for a in range(c + c, n + 1, c) if (a - c) & c == 0)
    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))  # 单点单整数,全文只有这一个 token
    print(count_pairs(n))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 04:05
 * update_at: 2026-10-08 04:05
 */
// main.cpp:一本通 1801《异或》。求 [1,n] 内满足 gcd(a,b) = a xor b 的无序数对个数。
// 与 main.py 同一算法:由等号链 gcd(a,b) = a-b = a xor b = c 把问题化为
// "枚举公约数 c 与其倍数 a,判断 (a-c) & c == 0",O(n log n)。
//
// 题意与规模:30% n<=1000,60% n<=10^5,100% n<=10^7;时限 1000ms / 128MB。
//
// 关键观察(等号链):
//   取 a > b(a = b 时 gcd = a 而 a xor a = 0,无解,故无序对与 a > b 一一对应)。
//   一方面 gcd(a,b) | (a-b) 故 gcd(a,b) <= a-b;
//   另一方面任意整数有 a xor b >= a-b(当且仅当 a & b == 0 且 b <= a 时取等)。
//   两式夹逼使 gcd(a,b) = a xor b 时三者相等:gcd(a,b) = a-b = a xor b =: c。
//   反过来,c 是 a 的约数且 (a-c) & c == 0 时 a = b + c 做加法不进位,
//   于是 a xor b = c,且 gcd(a,b) = gcd(a, a-c) = gcd(a, c) = c(因 c | a),条件成立。
//   每个合法无序对唯一对应 (c = gcd, a),枚举不会重复计数。

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

typedef long long ll;

int main() {
    ll n;                                  // 题目给定的上界,规模到 1e7,故用 ll
    if (scanf("%lld", &n) != 1) return 0;  // 空输入直接结束
    ll ans = 0;                            // 满足条件的无序对个数
    // 枚举公约数 c 与其倍数 a(a >= 2c,保证 b = a - c >= 1 且 b < a)
    for (ll c = 1; c + c <= n; ++c) {
        for (ll a = c + c; a <= n; a += c) {
            // (a-c) & c == 0 等价于 b + c 相加无进位,即 b xor a == c
            if (((a - c) & c) == 0) ++ans;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

  • 时间:外层 cc 枚举到 ⌊n/2⌋\lfloor n/2 \rfloor,内层枚举 cc 的倍数,共 ∑c⌊n/c⌋≈nln⁡n\sum_{c} \lfloor n/c \rfloor \approx n \ln n 次,每次常数次位运算,故 O(nlog⁡n)O(n \log n)。 n=107n = 10^7 时约 1.53×1081.53 \times 10^8 次循环,C++ 实测 56 ms(限时 1000 ms)。
  • 空间:只用 nn、ansans 两个标量,O(1)O(1) 额外空间,峰值内存与输入无关。
  • 与 Python 解法的关系:main.py 是同一算法、同一枚举顺序,只是把内层循环 换成生成器求和、用 n // 2 定上界。Python 单次循环比 C++ 慢约两个数量级, n=107n = 10^7 时实测约 3.7 s,超出 1000 ms 限时,存在 TLE 风险; 但按本仓库约定 Python 短解法允许 TLE,不允许把算法降级成暴力(暴力是 O(n2)O(n^2), 在 n=1000n = 1000 就已经很慢),因此保持同阶算法。

总结

  • 先用不等式夹逼,再动手枚举:本题的全部困难在于 n=107n = 10^7 时数对太多, 而 gcd⁡⩽a−b⩽a⊕b\gcd \leqslant a-b \leqslant a \oplus b 这条"除法/异或双重下界"直接把候选 从 O(n2)O(n^2) 压到 O(nlog⁡n)O(n \log n)。数论题里"先找不变量、再决定枚举对象"是通用套路。
  • 等号链比单个等号更有信息量:gcd⁡(a,b)=a⊕b\gcd(a,b) = a \oplus b 本身只是一个条件, 但两边分别有上下界后,条件就变成"三量同时取等",从而 c=a−bc = a-b 被唯一确定, 枚举维度从两维降到一维。
  • 整除 + 不进位 = 两个必要条件合起来是充要条件:c∣ac \mid a 保证 gcd⁡⩾c\gcd \geqslant c, b+cb + c 不进位保证 ⊕\oplus 等于 cc,而 a−b=ca - b = c 又压住 gcd⁡⩽c\gcd \leqslant c, 三面合围恰好封闭。写题解时把"必要性"和"充分性"两侧都写清楚,才能确认枚举不重不漏。
  • 复杂度看枚举量而不是答案量:答案只有 1.7×1071.7 \times 10^7 量级,但枚举是 nln⁡nn \ln n;两者都不是 O(n2)O(n^2),这正是能过题的原因。
  • 本题素材为网络重建:数据由自带生成脚本 data.py 产出(分层铺到 n=107n = 10^7 顶格), 题面与 UVA 12716 GCD XOR 同源,出题意图与官方原题可能略有偏差, 但结论与逐点实测一致。

图示解析

下图是第一层夹逼的几何含义:gcd⁡\gcd 从下方、异或从上方共同挤压 a−ba-b, 三者只有取等才可能同时成立。

flowchart LR
  A["gcd(a,b) = d"] --"d | (a-b) 故 d <= a-b"--> M["a - b"]
  C["a xor b"] --"任意整数有 a xor b >= a-b"--> M
  M --"夹逼使三者取等"--> E["c = gcd = a-b = a xor b"]
  E --> F["c 整除 a,且 (a-c) & c == 0"]
  F --> G["枚举 c 与倍数 a,计数"]

第二张图是枚举的结构:cc 从 1 到 n/2n/2,每个 cc 顺着倍数轴走一遍, 只保留"相加不进位"的 aa。

flowchart TD
  R["c = 1..n/2"] --> C1["c: 检查倍数 a = 2c, 3c, ... <= n"]
  C1 --> Q{"(a-c) & c == 0 ?"}
  Q --"是"--> Y["ans += 1(对应数对 a, a-c)"]
  Q --"否"--> N["跳过(异或 > c,或 gcd < c)"]

所谓"相加不进位",就是 b=a−cb = a - c 与 cc 的二进制 1 位置不相交, 此时 b+cb + c 的逐位加法不产生任何进位,异或与加法同值,b⊕c=ab \oplus c = a。 这个条件用一次 & 就能判定,也是整个 O(nlog⁡n)O(n \log n) 枚举里唯一的常数代价。