P10262 亲朋数：筛法求约数和与配对判重的数论实战

洛谷 P10262《亲朋数》这个题名，第一眼看上去不像传统数论题，倒像是哪个模拟赛临时起的名字。等把题面读完才发现，它考的是个老牌数学概念——亲和数对，国内有些地方也叫“相亲数”“好友数”。对正在备考冲刺的选手来说，这道题非常值得专门拿出来刷一遍：题面短，代码量不大，但把“筛法求约数和”和“配对判重”两个高频考点揉在了一起，坑还一个不少。

先讲清楚这道题在干什么。定义两个正整数 a 和 b，如果 a 的所有真因子（也就是除了 a 本身以外的所有约数）之和等于 b，同时 b 的所有真因子之和又恰好等于 a，那么 (a, b) 就构成一对“亲朋数”。最经典的例子是 220 和 284：220 的真因子和是 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284，284 的真因子和是 1 + 2 + 4 + 71 + 142 = 220。这个对称关系才是“亲朋”两个字的由来。这类题适合谁？正在准备算法竞赛、想把数论基础打扎实的选手都可以做，难度大约在普及组往上、提高组入门的位置，刚好用来练筛法和边界处理。

1. 题目核心：亲朋数到底在算什么

1.1 题面本质是“双向验证”

很多同学看到“求一个区间的所有亲朋数”第一反应是：那我先把每个数的真因子和算出来，再配对就行。思路方向没错，但题目真正的门槛在细节里。

首先是“真因子”三个字。约数包括 1 和自身，真因子必须把自身去掉。也就是说，对每个数 i，我们关心的其实是一个函数 f(i) = σ(i) - i，其中 σ(i) 表示 i 的所有约数之和。6 的约数和是 1 + 2 + 3 + 6 = 12，减掉自身以后 f(6) = 6，所以 6 满足 f(6) = 6，但它不能和任何“朋”配对，因为题目要求的是两个不同的数互为因子和。像 6、28、496 这种 f(n) = n 的数叫完全数，做题时要注意区分，别把它们当成非法输入，但也别把单个完全数算成一类“亲朋数对”。

然后是“双向验证”。判断一组 (a, b) 是否合法，必须同时满足 f(a) = b 且 f(b) = a。有些题解只判断了 f(a) = b，顺手把答案输出了，结果在边界数据上多出了一堆假数对。原因很简单：a 的因子和恰好等于 b，不代表 b 的因子和真的回到 a，两个条件缺一不可。

1.2 为什么这道题值得在冲刺阶段刷

这道题的考点组合非常典型：约数和计算、筛法优化、配对去重、越界保护、输出排序，全是比赛里最常碰到的“手滑重灾区”。我刷题圈子里有个共识：能一遍 AC 这种题的人，代码细节能力一般不会差；反之，平时只刷模板题、不看边界的人，很容易在这里卡住。

另外，“求约数和”这个概念不是孤立考点。约数个数、约数和、欧拉函数这些积性函数，在数论题里经常组团出现。把 P10262 吃透以后，再遇到“输出区间内约数和为某值的数”“统计约数和相等的对数”这类变形题，思路是可以直接迁移的。

2. 从朴素暴力的不可行到筛法思路

2.1 直接枚举为什么跑不动

先看最容易想到的暴力方案：对区间 [l, r] 里的每个数 a，单独用根号级别的枚举算 f(a)。求单个数的约数和，只需枚举 1 到 √a，遇到因子 d 就把 d 和 a / d 一起加进去，最后减掉 a 自己。这个方法写起来超级简单，但复杂度一算就露馅：

单个数求 f(a) 的复杂度：O(√a) 区间长度为 L 时：O(L · √r)

假设 r = 10^6，L = 10^5，那么大约要做 10^5 × 10^3 = 10^8 次运算，已经接近 C++ 一秒的极限；如果 r 到 10^7、区间再长一点，直接超时到没边。而且这只是算完了 f，后面还要再扫描一遍配对，总耗时更糟。

暴力不值得直接用来 AC，但它有个很实在的用途：对拍。写一个 O(√n) 的单点因子和函数，用来验证小数据范围里的筛法结果，非常方便。后面第 5 节我会专门讲这个。

2.2 因子贡献法：让因子主动去找它的倍数

既然“对每个数枚举因子”太难，那就反过来：对每个因子，让它主动去更新自己的倍数。

这个思路的历史相当悠久。埃氏筛之所以快，是因为“质数 p 去标记自己的倍数”时每个合数最多被几个质数标记到。这里我们借用同样的框架：从 i = 1 开始，把所有是 i 的倍数的数 j，都加上一个贡献 i。因为要的是真因子，所以 j 从 2i 开始，不要包含 j = i 那一项。

用生活化的类比解释就是：不要等着每个客户自己上报“我有哪些社交关系”，而是让每个因子像推销员一样，直接跑到所有客户门口登记一笔金额。每个因子 i 的客户就是 i 的倍数，它只需要沿着 i, 2i, 3i, … 这条线走一遍。

写成代码就是：

void init_era(int n) { // sum[x] 用来累计 x 的所有真因子之和 for (int i = 1; i * 2 <= n; ++i) { for (int j = i + i; j <= n; j += i) { sum[j] += i; } } }

外层循环为什么可以只到 n / 2？因为 i > n / 2 时，i 的最小真倍数 2i 已经超过 n，不可能再给任何范围内的数贡献因子。这个细节很多人容易忽略，写不写都不影响正确性，但写了能让常数稍微好看一点。

2.3 埃氏倍数筛的复杂度到底是多少

内层循环的总执行次数是：

n/2 + n/3 + n/4 + ... + n/n

这个式子约等于 n(1/2 + 1/3 + ... + 1/n)，也就是 n 乘以一个调和级数。调和级数的和大约是 ln(n) + γ，所以总复杂度是 O(n log n)。具体数量级可以估算：

这个复杂度不是线性，但接近线性，实际比赛里 n 在 10^6 级别时完全够用。如果出题人把范围开到了 10^7，埃氏倍数筛仍然可能通过，但就要注意常数优化了：数组要开成全局变量，循环尽量连续访问，编译开 O2。

3. 配对统计与完整题解

3.1 配对时最容易翻车的三个细节

筛完 f(a) 之后，配对部分看着简单，实际上有三个点特别容易写错。

第一，必须做“双向验证”。不能只写f[a] == b，要同时检查f[b] == a。否则像某些特殊数字，虽然 f(a) 恰好落在候选集合里，但反向不成立，就会被错误统计进去。

第二，要避免重复计数。区间里如果存在 (220, 284)，遍历到 a = 220 时能发现 b = 284，遍历到 a = 284 时又能发现 b = 220。如果不加限制，一组数对会被输出两次。最简单的方法是在遍历时只处理b > a的情况，这样每一对数对只会从较小的那个数开始访问到。这个技巧顺带也把 a = b 的完全数情况排除掉了，因为b > a对它们不成立。

第三，访问 f[b] 之前必须检查 b 是否还在合法范围内。假设当前 a = 999900，f(a) 算出来是 11000000，这个 b 可能已经超过区间右端点 r，甚至超过数组大小。如果不判b <= r就直接访问 f[b]，轻则读到下标越界，重则段错误。这里要注意 C++ 的短路求值：if (b > a && b <= r && f[b] == a)这个写法是安全的，因为 b > r 时不会访问数组。

3.2 完整 AC 代码（单次查询版本）

#include <bits/stdc++.h> using namespace std; const int MAXN = 10000000; // 根据题目范围调整 int sum[MAXN + 1]; // 全局数组，避免栈溢出 void init_era(int n) { for (int i = 1; i * 2 <= n; ++i) { for (int j = i + i; j <= n; j += i) { sum[j] += i; // i 是 j 的真因子 } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int l, r; cin >> l >> r; init_era(r); vector<pair<int, int>> ans; for (int a = l; a <= r; ++a) { int b = sum[a]; if (b > a && b <= r && sum[b] == a) { ans.push_back({a, b}); } } for (auto &p : ans) { cout << p.first << ' ' << p.second << '\n'; } return 0; }

如果题目只需要输出数对数量，把vector改成计数器即可。ans.size()就是答案。

3.3 输出与排序是否需要额外处理

因为遍历时是a从小到大，而且只保留了b > a的数对，所以输出的每一对数天然满足“第一个数小于第二个数，且按第一个数升序”。大多数题面如果要求输出数对，都会默认这个顺序。不过保险起见，交之前可以看下题面是否要求“按第一个数升序，若相同按第二个数升序”——上面的代码天然满足，不需要额外排序。

注意题目问法可能有细微差别：有的题是“输出区间内所有亲朋数”，有的是“输出对数”，还有的是“统计满足条件的数的个数”。这三种问法对应的只是最后统计方式不同，核心的筛法和判重逻辑完全一致。

4. 进阶优化：线性筛预处理约数和

4.1 线性筛为什么也能顺手求约数和

埃氏倍数筛的复杂度是 O(n log n)，虽然够用，但追求极致的时候还是想把它压到 O(n)。这就轮到线性筛登场了。

线性筛（欧拉筛）保证每个合数只会被它的最小质因子筛掉一次。如果在筛的过程中维护几个辅助信息，我们就可以同时求出每个数的约数和，而不需要单独跑一遍倍数循环。

这里用到一个数论概念：约数和函数 σ(n) 是积性函数。所谓积性，就是当 gcd(a, b) = 1 时，有 σ(ab) = σ(a) × σ(b)。我们没办法直接把 σ(i × p) 从 σ(i) 推出来，因为 i 和 p 不一定互质；但只要把“最小质因子那一整块”单独拆出来，就可以做到。

4.2 状态设计与递推公式

维护三个数组：

• sig[i]：i 的约数和。
• low[i]：i 的最小质因子 p 的最高次幂 p^k。比如 i = 12 = 2^2 × 3，low[12] = 4。
• pw[i]：1 + p + p^2 + ... + p^k，也就是最小质因子贡献的那一整块。比如 low[12] = 4，pw[12] = 1 + 2 + 4 = 7。

当用线性筛生成合数 x = i × p（p 是质数）时，分两种情况讨论。

情况一：p 没有在 i 中出现过，也就是 i % p != 0。此时 p 是 x 新增的最小质因子，而且 p 与 i 互质。直接累乘：

sig[x] = sig[i] × (p + 1) low[x] = p pw[x] = p + 1

情况二：p 已经在 i 中出现过，也就是 i % p == 0。设 i = p^k × m，其中 m 里没有 p 这个因子。那么 x = p^(k+1) × m。这个时候不能直接用 sig[i] 乘 (p + 1)，因为会重复计算。正确做法是：

low[x] = low[i] × p pw[x] = pw[i] × p + 1 sig[x] = sig[i / low[i]] × pw[x]

验证一下：i = 12 = 2^2 × 3，p = 2，x = 24。sig[12] = 1 + 2 + 3 + 4 + 6 + 12 = 28，low[12] = 4，pw[12] = 7。那么 low[24] = 4 × 2 = 8，pw[24] = 7 × 2 + 1 = 15，sig[24] = sig[12 / 4] × 15 = sig[3] × 15 = 4 × 15 = 60。而 24 的约数和确实是 1 + 2 + 3 + 4 + 6 + 8 + 12 + 24 = 60，完全正确。

最后别忘了，约数和包含自身。题目要的是真因子和，所以对所有 i 再执行一次sig[i] -= i即可。

4.3 线性筛版本完整代码

#include <bits/stdc++.h> using namespace std; const int MAXN = 10000000; bool isComp[MAXN + 1]; int primes[MAXN / 10], cnt; int sig[MAXN + 1]; int low[MAXN + 1]; int pw[MAXN + 1]; void init_linear(int n) { sig[1] = 1; for (int i = 2; i <= n; ++i) { if (!isComp[i]) { primes[cnt++] = i; low[i] = i; pw[i] = i + 1; sig[i] = i + 1; } for (int j = 0; j < cnt && 1LL * i * primes[j] <= n; ++j) { int x = i * primes[j]; isComp[x] = true; if (i % primes[j] == 0) { low[x] = low[i] * primes[j]; pw[x] = pw[i] * primes[j] + 1; sig[x] = sig[i / low[i]] * pw[x]; break; } else { low[x] = primes[j]; pw[x] = primes[j] + 1; sig[x] = sig[i] * pw[x]; } } } for (int i = 1; i <= n; ++i) { sig[i] -= i; // 转成真因子和 } }

注意i * primes[j]理论上不会溢出 int，但为了保险我还是喜欢转成 long long 再比较，这是个可以不加但加了更稳的习惯。

4.4 两种筛法的内存与速度对比

很多选手一看线性筛是 O(n)，就觉得它“全面优于”埃氏倍数筛，实际不然。线性筛虽然时间更优，但为了维护 low 和 pw 两个额外数组，内存占用涨得飞快。

所以在真实的比赛环境里，不是无脑选“复杂度更优”的那个。先看 n 的上限和内存限制，n 在 10^6 以下用哪个都行，n 到 10^7 就要权衡。如果内存限制是 64 MB，线性筛这套大概率会超；这时候埃氏倍数筛反而能活下来。这也是为什么我不建议只会一种写法就上考场。

5. 多组询问与更大数据规模的处理套路

5.1 多次询问只需要预处理一次

如果题目给了 Q 个询问，每个询问给一个 [l, r]，要求输出对应区间里的亲朋数对，最优做法肯定不是每个询问都重新筛一遍。

正确套路是离线处理：先把所有询问读进来，找到最大的右端点 Rmax，只对 Rmax 做一次筛法。然后预处理出全局范围内所有的亲朋数对，存到一个vector<pair<int, int>>里。之后对于每个询问，遍历这个 vector，把完全落在 [l, r] 内的数对统计出来。

为什么可以这样？因为全局数对的数量非常稀疏。10^6 范围内经典的亲和数对只有几对，10^7 范围内也不会爆炸增长。每次询问线性扫一遍这个 vector，代价远小于重新做一次筛法。

如果 Q 特别大，还可以把数对按第一维排序，用二分定位起点，再往后扫描直到超过 r。甚至可以用树状数组做离线二维统计，但说实话，竞赛里一般用不到这么复杂。能想到这里已经足够稳妥。

5.2 更大范围时的内存管理建议

n 到 10^7 的时候，int sum[MAXN + 1]是 40 MB，这是埃氏倍数筛能扛住的上限附近了。n 到 10^8 时，光一个 int 数组就是 400 MB，绝大多数 OJ 直接劝退。遇到这种极端数据，通常要转换思路：只保存所有质数，或者用分段筛，把区间切成小块，一次只处理一段。这属于更进阶的内容，P10262 大概率不会考到这么狠，但知道有这么回事，比临场慌神强。

还有个容易被新手忽略的点：数组不要开在函数内部。int sum[10000001]写在 main 函数里，会直接放到栈上，栈空间一般只有 8 MB 左右，瞬间爆栈。正确做法是放在全局区，或者用vector<int> sum(MAXN + 1)动态分配在堆上。我见过不少同学代码逻辑完全正确，就因为数组开在局部，样例都过不了，非常可惜。

5.3 用已知的经典亲和数对做自测

做完程序以后，建议拿几个已知的经典亲和数对验证一下：

(220, 284) (1184, 1210) (2620, 2924) (5020, 5564) (6232, 6368) (10744, 10856) (12285, 14595) (17296, 18416)

拿区间 [1, 20000] 测试，上面这些数对应当全部能被筛出来。如果少了哪一组，多半是筛法或者配对条件写错了；如果多出来奇怪的组合，就要检查双向验证和真因子的定义。用已知数对自测，比盲目对着题目样例猜快得多。

6. 我当时踩过的坑与常见错误速查

6.1 配对判重的踩坑实录

我第一次交这道题时，用的是最朴素的双向验证，但没加b > a，结果一组数对被输出了两次。当时我以为是筛法写错了，查了半天，最后把输出拉出来看才发现是重复计数。加一行if (b > a)就解决了。

第二次踩的坑更有代表性：我把区间右端点设得很大，但是没判b <= r就访问sum[b]。本地测试时只跑了小数据，一切正常；换到边界数据直接段错误。因为当 a 接近 r 时，它的真因子和很可能超过 r，一旦超过数组界限就是非法访问。这个教训让我养成了习惯：任何f[a]的结果当作数组下标使用之前，先确认它真的落在合法范围内。

还有一次是统计输出顺序的坑。题目要求“按第一个数升序排列”，因为我遍历的时候已经是 a 从小到大、b > a，所以天然满足。但如果在筛选数对时用了set或者先存了反过来的 pair，输出顺序就会变乱，需要在最后统一 sort 一下。顺带一提，结构体排序时最好把 first 设为较小的那个数，不然对判断也会出问题。

6.2 常见错误速查表

6.3 一个小技巧：把筛法和配对分开调试

调试这种题有个很省时间的习惯：先把筛法跑完，输出小范围的 sum 数组检查一遍，确认因子和算对了再去看配对逻辑。很多人喜欢一段代码里同时调两份逻辑，出了问题分不清是筛的错还是配对的错。分开调试看起来多写了一行输出，实际上能省下一晚上的排查时间。

最后说点我自己的体会。这种“题面简单，实现坑密”的题，恰恰是最能检验基础功的试金石。刷题不必总追求那种看完题解恍然大悟的难题，把 P10262 这类题练到随手就能 AC，筛法数组、边界判断、判重输出这些基本功就真正长在身上了。以后再遇到“统计区间内满足某某对称关系的数对”，核心套路都是同一套：预处理因子和，配对时保持 a < b，访问数组前先判界。这三个点记住了，类似题目基本不会翻车。