解题思路

先理解“真因子”：能整除 a、但不等于 a 本身的自然数。例如 12 的真因子是 1、2、3、4、6，它们的和是 16。

亲和数：如果 a 的真因子之和等于 b，而且 b 的真因子之和又等于 a，那么 a、b 就互称“亲和数”，并且要求 a ≠ b。

比如最小的亲和数是 220 和 284：

• 220 的真因子：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
• 284 的真因子：1 + 2 + 4 + 71 + 142 = 220
• 你中有我，我中有你，所以 220 和 284 是一对亲和数！

题目没有输入，让我们直接求出最小的一对亲和数并输出（要求 a < b）。

怎么找呢？用“暴力枚举”：

1. 写一个函数 yinzi(x)，从 1 到 x-1 试，能整除 x 的数都累加起来，返回真因子之和；
2. 从 a = 2 开始从小到大枚举：算 b = yinzi(a)；
3. 检查 b 是否大于 a（保证 a < b），并且 yinzi(b) == a；
4. 第一个满足条件的 a 对应的就是最小的亲和数对。

因为是从小到大枚举，第一次找到的一定是答案，直接输出并结束程序。

参考代码

// P4598 亲和数：从 2 开始找，输出最小的一对亲和数(a<b)
#include <iostream>
using namespace std;

// 返回 x 的所有真因子之和（不含 x 本身）
int yinzi(int x) {
    int s = 0;
    for (int i = 1; i < x; i++)   // 从 1 试到 x-1
        if (x % i == 0) s += i;   // i 能整除 x，i 就是 x 的真因子
    return s;
}

int main() {
    for (int a = 2; ; a++) {      // 从小到大枚举 a
        int b = yinzi(a);         // a 的真因子之和为 b
        if (b > a && yinzi(b) == a) {  // b 大于 a，且 b 的真因子之和等于 a
            cout << a << " " << b << endl;
            return 0;             // 找到最小的亲和数对，结束程序
        }
    }
}

复杂度分析

枚举从小到大进行，在 a = 220 时就能找到答案，循环次数很少。每次计算真因子之和 yinzi(x) 要试到 x，时间是 O(x)。总的来说程序运行非常快，空间只用几个变量，是 O(1)。