欧拉计划 21

Amicable numbers

题目描述

记 为 的所有真约数（小于 且整除 的正整数）之和。如果 ，且 ，那么 和构成一个 亲和数对， 和 被称为亲和数。

求所有小于 的亲和数的和。

思路

欧拉筛求解素因子和
因子和公式

代码

// 素数筛算法求解因子和问题
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 10000;
int prime[N + 5];
int f[N + 5];
int cnt[N + 5]; // cnt[i] 记录 i 最小素因子的幂次

void init() {
    for (int i = 2; i <= N; i++) {
        if (!prime[i]) {
            prime[++prime[0]] = i;
            f[i] = i + 1;
            cnt[i] = 1;
        }
        for (int j = 1; j <= prime[0] && prime[j] * i < N; j++) {
            prime[prime[j] * i] = 1;
            if (i % prime[j]) {  // i 与 prime[j] 互素
                f[i * prime[j]] = f[i] * f[prime[j]];
                cnt[i * prime[j]] = 1;
            }
            else {
                f[i * prime[j]] = f[i] / (pow(prime[j], cnt[i] + 1) - 1) * (pow(prime[j], cnt[i] + 2) - 1);  // 等比数列求和公式
                cnt[i * prime[j]] = cnt[i] + 1;
                break;
            }
        }
    }
}

int main() {
    init();
    for (int i = 2; i < N; i++) f[i] -= i;
    
    int ans = 0;
    for (int i = 2; i < N; i++) {
        if (f[i] != i && f[f[i]] == i) {
            ans += i;
            printf("%d %d\n", i, f[i]);
        }
    }
    
    printf("%d\n", ans);
    return 0;
}