解题思路

先来理解两个新概念：

• 因子：能整除某个数的自然数，但不含它本身。比如 12 的因子有 1、2、3、4、6（不算12自己）。
• 亲和数：如果 a 的因子之和等于 b，而 b 的因子之和又等于 a，且 a≠b，那么 a、b 就是一对"亲和数"。

题目要我们找到最小的那一对亲和数，并且按 a<b 输出。这道题没有输入，直接输出答案即可。

做法是从小到大一个一个试：

1. 写一个 judge(x) 函数，负责计算 x 的因子之和；
2. 从 a=2 开始，算出 b = judge(a)；
3. 检查：b 是不是大于 a？judge(b) 是不是又等于 a？两个条件都满足，就说明找到了一对亲和数！
4. 因为我们是从小到大找的，所以找到的第一对就是最小的亲和数。

顺便验证一下：a=220 的因子和是 1+2+4+5+10+11+20+22+44+55+110 = 284，而 284 的因子和是 1+2+4+71+142 = 220，所以 220 和 284 正是最小的亲和数对！

打个比方：两位好朋友互相给对方写信，信的"分量"一模一样——a 把所有因子加起来恰好等于 b，b 把所有因子加起来又恰好等于 a，真是一对"心有灵犀"的数字呀！

参考代码

// P4605 最小的亲和数：找出最小的一对亲和数(a<b)并输出
#include <iostream>
using namespace std;

// judge函数：计算自然数x的因子之和（因子不含x本身）
int judge(int x) {
    int s = 0;
    for (int i = 1; i < x; i++) {
        if (x % i == 0) s += i;  // i能整除x，说明i是x的因子
    }
    return s;
}

int main() {
    // 从小到大找第一对a、b，满足b的因子之和等于a，且a不等于b
    for (int a = 2; a < 100000; a++) {
        int b = judge(a);              // b是a的因子之和
        if (b > a && judge(b) == a) {  // 要求a<b，且b的因子之和等于a
            cout << a << " " << b << endl;
            return 0;
        }
    }
    return 0;
}

复杂度分析

• judge(x) 要枚举 1 到 x-1 的所有数来判断是否是因子，所以单次调用是 O(x)。
• 主程序从小到大找，最快在 a=220 时就找到答案，实际运行非常快。最坏情况下大约要尝试 a 个候选、每个调用 judge 两次，整体可看作 O(a²)（a 是找到答案时的数）。
• 我们只用了几个变量，空间复杂度是 O(1)。

虽然理论上要找很多次，但答案很快就出现，所以程序运行飞快。