Non-abundant sums

題目描述

記 為 的所有真約數(shù)（小于 且整除 的正整數(shù)）之和。
若 ，則稱之為虧數(shù)；反之，則稱之為盈數(shù)。

由于 是最小的盈數(shù)，它的真約數(shù)之和為 ，所以最小的能夠表示成兩個(gè)盈數(shù)之和的數(shù)是 。通過數(shù)學(xué)分析可以得出，所有大于 的數(shù)都可以被寫成兩個(gè)盈數(shù)的和。

求所有不能被寫成兩個(gè)盈數(shù)之和的正整數(shù)之和。

思路

跟歐拉21 很相似
根據(jù)歐拉篩每個(gè)合數(shù)都被自身最小素因子篩到的特性
結(jié)合利用因子和公式，可以在線性時(shí)間內(nèi)求出所有數(shù)的因子和

代碼

// 素?cái)?shù)篩算法求解因子和問題
#include <cstdio>

const int N = 28123;
int prime[N + 5];
int f[N + 5];
int cnt[N + 5]; // cnt[i] 記錄 i 最小素因子的冪次
bool mark[N + 5];

void init() {
    for (int i = 2; i <= N; i++) {
        if (!cnt[i]) { // 如果是合數(shù)，則 cnt[i] 已經(jīng)被標(biāo)記過
            prime[++prime[0]] = i;
            f[i] = i + 1;
            cnt[i] = i;
        }
        for (int j = 1; j <= prime[0] && prime[j] * i <= N; j++) {
            if (i % prime[j]) {  // i 與 prime[j] 互素
                cnt[i * prime[j]] = prime[j];  // prime[j] 為 i * prime[j] 的最小素因子
                f[i * prime[j]] = f[i] * f[prime[j]];
            }
            else {
                cnt[i * prime[j]] = cnt[i] * prime[j];
                f[i * prime[j]] = f[i] * (cnt[i * prime[j]] * prime[j] - 1)
                                  / (cnt[i * prime[j]] - 1);  // 等比數(shù)列求和公式
                break;
            }
        }
    }
}

int main() {
    init();
    int k = 0;
    for (int i = 2; i <= N; i++) {
        if (f[i] > (i << 1)) f[k++] = i;
    }
    
    for (int i = 0; i < k; i++) {
        for (int j = i; j < k; j++) {
            if (f[i] + f[j] > N) break;
            mark[f[i] + f[j]] = true;
        }
    }
    
    int ans = 0;
    for (int i = 0; i <= N; i++) {
        if (!mark[i]) ans += i;
    }
    printf("%d\n", ans);
    return 0;
}