好朋友

题意

给出一个整数 s，要求找出第一对友好数 (A, B)，满足较小的那个数不小于 s。

这里的友好关系定义为：

A 的真约数和等于 B
B 的真约数和等于 A
A != B

思路

先看一个可以直接验证想法的朴素解：

从 s 开始枚举每个 A，直接枚举 1..A-1 求真约数和，得到 B，再检查 sum(B) 是否回到 A。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include <bits/stdc++.h>
using namespace std;

int sum_proper_divisors(int x) {
    int sum = 0;
    for (int d = 1; d < x; d++) {
        if (x % d == 0) sum += d;
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s;
    cin >> s;

    for (int a = s;; a++) {
        int b = sum_proper_divisors(a);
        if (b <= a) continue;
        if (sum_proper_divisors(b) == a) {
            cout << a << ' ' << b << '\n';
            return 0;
        }
    }

    return 0;
}

这个做法的瓶颈在于求真约数和太慢。正式做法利用约数成对出现的性质，只枚举到 sqrt(x)，就能在 $O(sqrt x)$ 时间里算出一个数的真约数和。

为了避免同一对数重复输出，只保留 A < B 的情况。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include <bits/stdc++.h>
using namespace std;

int sum_proper_divisors(int x) {
    if (x == 1) return 0;
    int sum = 1;
    for (int d = 2; 1LL * d * d <= x; d++) {
        if (x % d) continue;
        sum += d;
        if (d * d != x) sum += x / d;
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s;
    cin >> s;

    for (int a = s;; a++) {
        int b = sum_proper_divisors(a);
        if (b <= a) continue;
        if (sum_proper_divisors(b) == a) {
            cout << a << ' ' << b << '\n';
            return 0;
        }
    }

    return 0;
}

复杂度

一次求真约数和的复杂度是 $O(sqrt x)$ 。从 s 开始向上搜索到答案前，需要做若干次这样的判断。空间复杂度是 $O(1)$ 。

总结

这题本质上是“枚举 + 真约数和判定”。关键在于用平方根试除更快地求出约数和。

目录

题意

思路

代码

复杂度

总结