亲和数

题目描述

自然数 $n$ 的真因子是指所有能整除 $n$ 且不等于 $n$ 的自然数。例如 $12$ 的真因子为 $1,2,3,4,6$ ，它们的和是 $16$ 。

若 $a$ 的真因子之和为 $b$ ，且 $b$ 的真因子之和又等于 $a$ ，并且 $a<b$ ，则称 $a,b$ 为一对"亲和数"。求最小的一对亲和数。

无输入。输出一行： $a$ 和 $b$ ，中间一个空格。

思路

写 sigma(n) 求 $n$ 的真因子和（因子成对出现，枚举 $d\le\sqrt n$ ，命中时把 $d$ 和 $n/d$ 两端一起收，完全平方数只收一次）；再从 $a=2$ 起递增枚举，第一次出现 $\sigma(\sigma(a))=a$ 且 $\sigma(a)\neq a$ 的 $a$ 即答案中较小者（完全数需排除）。

参考代码

Python 版：

python

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
33
34
35
36
37
38#!/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-09-29 21:15
# update_at: 2026-09-29 21:21

from functools import cache
from itertools import count
from math import isqrt


@cache
def divisor_sum(n: int) -> int:
    """n 的真因数和（所有小于 n 的因子之和）。

    因子成对出现：若 d 是因子，则 n // d 也是；所以只枚举 d <= sqrt(n)，
    每对 (d, n // d) 各收一次。1 是 n >= 2 时必有的真因子，单独计入；
    n 是完全平方数时 sqrt(n) 是自己的搭档，`d * d != n` 保证它只算一次。
    """
    if n == 1:
        return 0
    low = [d for d in range(2, isqrt(n) + 1) if n % d == 0]
    return 1 + sum(low) + sum(n // d for d in low if d * d != n)


def solve() -> None:
    # 无输入。定义要求 a = sigma(sigma(a)) 且 a != sigma(a)；
    # 从小到大枚举 a，第一次命中的 a 就是较小者（若 b < a 早就以 b 为 a 命中了）。
    for a in count(2):
        b = divisor_sum(a)
        if b != a and divisor_sum(b) == a:
            print(a, b)
            break


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
33
34
35
36
37
38
39
40/**
 * 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-05 03:44
 * update_at: 2026-10-05 03:44
 */
#include <cstdio>
#include <cmath>

typedef long long ll;

// sigma(n)：n 的真因数和（不含 n 本身的因子之和）
// 因因子成对出现：d 是因子则 n/d 也是，所以只枚举 d<=sqrt(n)；
// 每对 (d, n/d) 各收一次；1 单独计入；n 为完全平方数时 sqrt(n) 是自己的搭档，
// d*d==n 时只算一次。
ll sigma(ll n) {
    if (n == 1) return 0;
    ll s = 1; // 1 必为真因子
    ll r = (ll) sqrt((long double) n); // sqrt 取下整用于 d<=r 枚举
    for (ll d = 2; d <= r; ++d) {
        if (n % d == 0) {
            s += d;
            if (d * d != n) s += n / d; // d* d != n 保证完全平方数只收一次
        }
    }
    return s;
}

int main() {
    // 题目无输入；a 从 2 起递增枚举，第一次命中 sigma(sigma(a))==a 且 sigma(a)!=a 即最小解
    for (ll a = 2; ; ++a) {
        ll b = sigma(a);
        if (b != a && sigma(b) == a) {
            printf("%lld %lld\n", a, b);
            break;
        }
    }
    return 0;
}

目录

题目描述

思路

参考代码