題目大意

判定一個數字的因數總和與本身的大小關係。

題解

如果能快速獲得一個數字的質因數分解，就能使用高中課本公式計算一個數字的因數總和。由於一個數字的質因數很少，因此本題的關鍵在於如何做質因數分解。

考量到雖然輸入範圍是 1012 量級，但側資比數比較少，約 1000 筆，因此這裡使用了較簡單的建表法來處理。使用建表法的話，能夠在 O(π(N))∈O(nln⁡n) 計算完畢，剛好能壓線過這一題。

如果使用 Pollard’s Rho Algorithm 拆解可以進一步的加速到期望 O(N4)，但程式碼長度會變得很攏長，有興趣的話再寫一篇吧。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    const ll mx = 100'0000;
    vector<bool> isp(mx + 1, true);
    vector<ll> primes;

    isp[0] = isp[1] = false;
    for (ll i = 2; i <= mx; ++i) {
        if (isp[i]) {
            primes.emplace_back(i);

            for (ll j = i * i; j <= mx; j += i)
                isp[j] = false;
        }
    }

    int T;
    ll N;
    vector<ll> factor;
    ll sum, tmp;

    cin >> T;
    while (T--) {
        cin >> N;

        factor.clear();
        sum = 1;

        tmp = N;

        for (ll p : primes) {
            if (tmp < p)
                break;

            while (tmp % p == 0) {
                factor.emplace_back(p);
                tmp /= p;
            }
        }
        if (tmp > 1)
            factor.emplace_back(tmp);

        int FN = factor.size();
        for (int i = 0; i < FN;) {
            ll base = factor[i];

            ll pw = 1;
            ll psum = 1; // p^0

            while (i < FN && factor[i] == base) {
                i++;

                pw *= base;
                psum += pw;
            }

            sum *= psum;
        }

        sum -= N;
        if (sum == N)
            cout << "perfect" << '\n';
        else if (sum > N)
            cout << "abundant" << '\n';
        else
            cout << "deficient" << '\n';
    }
}

OJ 連結

連結：https://zerojudge.tw/ShowProblem?problemid=c204
連結：https://zerojudge.tw/ShowProblem?problemid=c203 (簡易版)