ZeroJudge 解題筆記：c184. 盈虧互補

作者：王一哲
日期：2025年8月9日


ZeroJudge 題目連結：c184. 盈虧互補

解題想法

先找出 n 包含 1 的因數 fac 及加總 facSum，如果 facSum 等於 n，n 是完全數；如果 facSum 不等於 n，還要再找 facSum 的因數 fac2 及加總 facSum2，如果 facSum2 等於 n，則兩者是友好數。

Python 程式碼

用 set 儲存因數，用 join 組合要輸出的因數加總算式。使用時間約為 39 ms，記憶體約為 3.5 MB，通過測試。

n = int(input())  # 要測試數字 n
fac = {1}  # 儲存 n 的因數，先放入 1
for i in range(2, int(n**0.5)+1):
    if n%i == 0:
        fac.add(i)
        fac.add(n//i)
facSum = sum(fac)  # n 的因數加總
print("+".join(map(str, sorted(fac))) + "=" + f"{facSum:d}")  # 印出 n 的因數及加總
if n == facSum:  # 如果 n 等於 facSum
    print(f"{n:d} is perfect.")  # n 是完全數
elif len(fac) == 1:  # 如果 fac 只有 1
    print("=0")  # 印出 =0
    print(f"{n:d} has no friends.")  # 不可能有友好數
else:  # 其它狀況
    n2 = facSum  # 要檢測 facSum 是否為友好數
    fac2 = {1}  # 儲存 n2 的因數，先放入 1
    for i in range(2, int(n2**0.5)+1):
        if n2%i == 0:
            fac2.add(i)
            fac2.add(n2//i)
    facSum2 = sum(fac2)  # n2 的因數加總
    print("+".join(map(str, sorted(fac2))) + "=" + f"{facSum2:d}")  # 印出 n2 的因數及加總
    if facSum2 == n:  # 如果 facSum2 等於 n，兩者是友好數
        print(f"{n:d} and {n2:d} are friends.")
    else:  # 否則 n 沒有友好數
        print(f"{n:d} has no friends.")

C++ 程式碼

使用時間約為 3 ms，記憶體約為 284 kB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 要測試數字 n
    vector<int> fac = {1};  // 儲存 n 的因數，先放入 1
    int r = (int)sqrt(n), facSum = 1;  // n 的平方根整數部分，因數加總
    if (n > 1) {  // n 大於 1 才需要找其它因數
        for(int i=2; i<=r; i++) {
            if (n%i == 0) {  // 如果 i 是因數
                fac.push_back(i);  // 將 i 加入 fac
                fac.push_back(n/i);  // 將 n/i 加入 fac
                facSum += i + n/i;  // 更新 facSum
            }
        }
        if (r*r == n) {  // 如果 n 是平方數
            fac.pop_back();  // 移除最後一項
            facSum -= r;  // facSum 減去 r
        }
        sort(fac.begin(), fac.end());
    }
    int m = (int)fac.size();  // n 的因數數量 m
    if (m == 1) {  // 特例，n 是質數
        puts("1=1");  // 除了 n 以外的因數只有 1
    } else if (m == 2) {  // 2 個因數
        printf("%d+%d=%d\n", fac[0], fac[1], facSum);
    } else {  // 3 個以上的因數
        printf("%d", fac[0]);
        for(int i=1; i<m-1; i++) printf("+%d", fac[i]);
        printf("+%d=%d\n", fac[m-1], facSum);
    }
    if (n == facSum) {  // 如果 n 等於 facSum
        printf("%d is perfect.\n", n);  // n 是完全數
    } else if (m == 1) {  // 如果 fac 只有 1
        puts("=0");  // 印出 =0
        printf("%d has no friends.\n", n);  // 不可能有友好數
    } else {  // 其它狀況
        int n2 = facSum;  // 要檢測 facSum 是否為友好數
        vector<int> fac2 = {1};  // 儲存 n2 的因數，先放入 1
        int r2 = (int)sqrt(n2), facSum2 = 1;  // n2 的平方根整數部分，因數加總
        if (n2 > 1) {
            for(int i=2; i<r2; i++) {
                if (n2%i == 0) {  // 如果 i 是因數
                    fac2.push_back(i);  // 將 i 加入 fac
                    fac2.push_back(n2/i);  // 將 n/i 加入 fac
                    facSum2 += i + n2/i;  // 更新 facSum
                }
            }
            if (r2*r2 == n2) {  // 如果 n2 是平方數
                fac2.pop_back();  // 移除最後一項
                facSum2 -= r2;  // facSum2 減去 r2
            }
            sort(fac2.begin(), fac2.end());
        }
        int m2 = (int)fac2.size();  // n2 的因數數量 m2
        if (m2 == 1) {  // 特例，n2 是質數
            puts("1=1");  // 除了 n2 以外的因數只有 1
        } else if (m2 == 2) {  // 2 個因數
            printf("%d+%d=%d\n", fac2[0], fac2[1], facSum2);
        } else {  // 3 個以上的因數
            printf("%d", fac2[0]);
            for(int i=1; i<m2-1; i++) printf("+%d", fac2[i]);
            printf("+%d=%d\n", fac2[m2-1], facSum2);
        }
        if (facSum2 == n) {  // 如果 facSum2 等於 n，兩者是友好數
            printf("%d and %d are friends.\n", n, n2);
        } else {  // 否則 n 沒有友好數
            printf("%d has no friends.\n", n);
        }
    }
    return 0;
}