M29918: 求亲和数

implementation, math, number theory, http://cs101.openjudge.cn/practice/29918/

遥远的古代，人们发现某些自然数之间有特殊的关系：设有两个数a和b，若a的所有除本身以外的因数之和等于b，b的所有除本身以外的因数之和等于a，则称a、b是一对亲和数。

例如220和284： 220的真因数包括：1,2,4,5,10,11,20,22,44,55,110. 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 284的真因数包括：1,2,4,71,142. 1 + 2 + 4 + 71 + 142 = 220 所以220和284是一对亲和数。

输入

一个正整数n，1<=n<=100000。

输出

所有亲和数对"a b"，满足a和b均小于等于n。每个亲和数对占一行，两个数之间用一个空格隔开，较小数在前，较大数在后。对于多个亲和数对，以较小数递增的顺序输出它们。

样例输入

样例输出

220 284
1184 1210

提示

implementation, brute force

来源

yan

1165ms

python

import math

def sum_of_divisors(x):
    s = 1

    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            s += i
            if i != x // i:  # 避免平方根重复加
                s += x // i
    return s if x > 1 else 0  # 特殊情况：1没有真因数

def find_amicable_pairs(n):
    for a in range(2, n + 1):
        b = sum_of_divisors(a)

        if b > a and b <= n and sum_of_divisors(b) == a:
            print(a, b)


n = int(input())
find_amicable_pairs(n)

时间复杂度是 O(n^3/2 )

逆向思维，考虑倍数，将每个i加到其小于n的倍数里。

一个数 i，必定是所有 i 的倍数的真因子。
用类似筛素数的想法，对每个数处理它的倍数。178ms。

python

n = int(input())
divsum = [0] * (n + 1)

# 计算每个数的真因子和（不包括自己）
for i in range(1, n // 2 + 1):
    for j in range(2 * i, n + 1, i):
        divsum[j] += i

# 找亲和数对
for a in range(2, n + 1):
    b = divsum[a]
    if b > a and b <= n and divsum[b] == a:
        print(a, b)

“对每个数 i，把它加到它所有倍数 j（除了它自己）的真因子和中。”
这样每次外层循环处理一个「因子」，内层循环批量更新它影响的所有数的“真因子和”。
时间复杂度是 O(nlogn)

979ms

python

import math

cache = {}  # 记忆化缓存，避免重复计算

def sum_of_divisors(x):
    if x in cache:        # 已计算过直接返回
        return cache[x]
    if x <= 1:            # 1 没有真因子
        return 0

    ans = 1
    for i in range(2, int(math.isqrt(x)) + 1):   # 用 isqrt，避免浮点
        if x % i == 0:
            ans += i
            if i != x // i:
                ans += x // i
    cache[x] = ans        # 存入缓存
    return ans


def find_amicable_pairs(n):
    for a in range(2, n + 1):
        b = sum_of_divisors(a)
        if b > a and b <= n and sum_of_divisors(b) == a:
            print(a, b)


n = int(input())
find_amicable_pairs(n)

18ms

python

import sys

# oeis.org
dict1 = {220: 284, 1184: 1210, 2620: 2924, 5020: 5564, 6232: 6368, 10744: 10856, 12285: 14595, 17296: 18416, 63020: 76084, 66928: 66992, 67095: 71145, 69615: 87633, 79750: 88730}

n = int(sys.stdin.readline())

for key in sorted(dict1.keys()):
    if key <= n and dict1[key] <= n:
        print(key, dict1[key])

M29918: 求亲和数 ​

M29918: 求亲和数