HDU 1406 完數：篩法預計算因子和

題目

完數定義：大於 1 的正整數，其所有真因子之和等於自身。如 6=1+2+3，28=1+2+4+7+14。給定區間 [a, b]，求區間內完數個數。多測試用例，以 EOF 結束。

篩法思路

類比埃氏篩，對每個 i 從 2 遍歷到 MAXN/2，將 i 加到其所有倍數的因子和中：

const int MAXN = 10000;
int sum[MAXN] = {0};

void sieve() {
    for (int i = 2; i <= MAXN/2; ++i)
        for (int j = i*2; j <= MAXN; j += i)
            sum[j] += i;
}

初始 sum[] 為 0，經篩選後 sum[x] 即為 x 的所有真因子之和 (不含 x 本身)。完數條件：sum[x] == x。

查詢處理

預處理完後，每個測試用例直接掃描 [a, b] 計數：

int main() {
    sieve();
    int a, b;
    while (scanf("%d%d", &a, &b) == 2) {
        if (a > b) swap(a, b);
        int cnt = 0;
        for (int i = a; i <= b; ++i)
            if (sum[i] == i) ++cnt;
        printf("%d\n", cnt);
    }
}

複雜度

• 預處理：O(N log log N) ≈ 10^4 規模極快
• 查詢：O(b-a+1) 每用例
• 空間：O(N)

注意事項

• 題目保證 a,b ≤ 10000，MAXN 設 10001 即可。
• 輸入可能 a > b，需交換。
• 1 不是完數 (定義要求大於 1)，篩法自然不計入。