HDU 2040 親和數問題 C++ 解法詳解

題目背景

杭電 HDU 2040 題目要求判斷兩個正整數是否為親和數。若兩數互為對方真因子之和，則稱為親和數對，輸出 YES，否則輸出 NO。

核心算法邏輯

解題關鍵在於計算某數的所有真因子之和（不包含自身）。算法步驟：

1. 遍歷 1 到 n-1，累加能整除 n 的因子
2. 判斷 sum(a) == b 且 sum(b) == a
3. 雙向滿足才輸出 YES

完整代碼實現

#include <iostream>
using namespace std;

long long Test(long long n) {
    long long sum = 0;
    for (long long i = 1; i < n; ++i) {
        if (n % i == 0) sum += i;
    }
    return sum;
}

int main() {
    long long n;
    cin >> n;
    while (n--) {
        long long a, b;
        cin >> a >> b;
        if (Test(a) == b && Test(b) == a)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

優化建議

• 因子遍歷可優化至 √n，成對累加
• 預計算常用範圍內的因子和表
• 注意 long long 防止大數溢出

本題考察基礎數論與枚舉優化，是 ACM 入門經典題型。