Amicable numbers

題目描述

記 為 的所有真約數(shù)（小于 且整除 的正整數(shù)）之和。如果 ，且 ，那么 和構(gòu)成一個(gè) 親和數(shù)對(duì)， 和 被稱為親和數(shù)。

求所有小于 的親和數(shù)的和。

思路

歐拉篩求解素因子和
因子和公式

代碼

// 素?cái)?shù)篩算法求解因子和問題
#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);  // 等比數(shù)列求和公式
                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;
}