由 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
形式化题目
给定正整数
无序意味着
样例
| 是否相等 | |||
|---|---|---|---|
只有
数据规模:30% 的测试点
正解
思路
朴素做法。 对每对
工具:一次夹逼。 设
- 整除方向。
且 ,所以 ,于是 。 (注意这是"约数不超过被它整除的数",等号当且仅当 。) - 异或方向。 对任意整数
,把 与 按位看: 加法中 的每一个 1 在 中有对应位就产生进位,而进位只会被异或"抹掉", 抵消不了减法;可以证明 。
把两个不等式拼在题目条件上:
夹逼迫使三处全部取等:
这一条把"两个全局量相等"的判定,压缩成了"差与公约数相等"的差一判定:
原来要在所有数对里撒网,现在
把等号链读成枚举方式。 记
反过来验证这个刻画是否"充要"。若
- 第二式说明
与 的低位 1 不重叠,加法 全程无进位, 故 处 ; - 又
且 ,故 ;而 , 所以 。
两边都是充要的,于是得到一条只需枚举一对
每个合法无序对
会不会重复计数? 不会。
为什么这样快。 枚举量是
比
以
实际入选的规模可以看真实数据:
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:外层
枚举到 ,内层枚举 的倍数,共 次,每次常数次位运算,故 。 时约 次循环,C++ 实测 56 ms(限时 1000 ms)。 - 空间:只用
、 两个标量, 额外空间,峰值内存与输入无关。 - 与 Python 解法的关系:
main.py是同一算法、同一枚举顺序,只是把内层循环 换成生成器求和、用n // 2定上界。Python 单次循环比 C++ 慢约两个数量级,时实测约 3.7 s,超出 1000 ms 限时,存在 TLE 风险; 但按本仓库约定 Python 短解法允许 TLE,不允许把算法降级成暴力(暴力是 , 在 就已经很慢),因此保持同阶算法。
总结
- 先用不等式夹逼,再动手枚举:本题的全部困难在于
时数对太多, 而 这条"除法/异或双重下界"直接把候选 从 压到 。数论题里"先找不变量、再决定枚举对象"是通用套路。 - 等号链比单个等号更有信息量:
本身只是一个条件, 但两边分别有上下界后,条件就变成"三量同时取等",从而 被唯一确定, 枚举维度从两维降到一维。 - 整除 + 不进位 = 两个必要条件合起来是充要条件:
保证 , 不进位保证 等于 ,而 又压住 , 三面合围恰好封闭。写题解时把"必要性"和"充分性"两侧都写清楚,才能确认枚举不重不漏。 - 复杂度看枚举量而不是答案量:答案只有
量级,但枚举是 ;两者都不是 ,这正是能过题的原因。 - 本题素材为网络重建:数据由自带生成脚本
data.py产出(分层铺到顶格), 题面与 UVA 12716 GCD XOR 同源,出题意图与官方原题可能略有偏差, 但结论与逐点实测一致。
图示解析
下图是第一层夹逼的几何含义:
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,计数"]
第二张图是枚举的结构:
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)"]
所谓"相加不进位",就是 & 就能判定,也是整个