1390. 四因数

思路

題目要找到有四個因數的數字，並將滿足條件的數字的所有因數相加。
而每個數字的因數都必定包含 1 跟自己，這樣就是兩個（1 是特例，但此題不需要考慮），
因此就是要先判斷這個數字能不能找到剛好一種的分解方式。
x = a * b，其中a, b != 1 且 a, b != x。

我們能用找質數的埃氏篩法，稍微修改之後用以找到因數合，以及共有多少因數。
舉例來說，現在要找1 ~ 10當中所有數字的因數合以及有多少因數。
用兩層迴圈，外層i，內層j。
i = 1，這時1 ~ 10都是 1 的倍數。
i = 2，這時2, 4, 6, 8, 10 都是 2 的倍數。
i = 3，這時3, 6, 9 都是 3 的倍數。
i = x，這時x, 2x, 3x ...都是 i 的倍數。
因此用兩層迴圈計算出因數合與因數作為判斷依據。
題目有給數據範圍，因此在初始化時，立刻先將表格建立起來，以供後續查找。

程式碼

const int MX = 1e5;
int factor[MX + 1];
int factor_sum[MX + 1];
int init = []{
    for(int i = 1; i <= MX; ++i) { // 如果想要優化可以從 2 開始，不過答案那邊就要修改
        for(int j = i; j <= MX; j += i) {
            factor[j]++;
            factor_sum[j] += i;
        }
    }
    return 0;
}();
class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int res = 0;
        for(int num : nums) {
            if(factor[num] == 4) { // 如果篩選從 2 開始, 需要修改為 3,
                res += factor_sum[num]; // 同上，需要額外加 1
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(MX\log{MX})$($MX + MX / 2 + MX / 3 + ...$)
• 空間複雜度：$O(MX)$