题目描述

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数，则返回 0。

样例

输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

限制

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

算法

(暴力枚举) $O(n \sqrt m)$

1. 枚举每个数字，暴力在平方根时间内找到所有约数的个数以及约数和。

时间复杂度

• 每个数字 $m$ 都需要 $O(\sqrt m)$ 的时间，故总时间复杂度为 $O(n \sqrt m)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    pair<int, int> check(int x) {
        int cnt = 0, tot = 0;
        for (int i = 1; i * i <= x; i++)
            if (x % i == 0) {
                cnt++;
                tot += i;
                if (i * i != x) {
                    cnt++;
                    tot += x / i;
                }
            }

        return make_pair(cnt, tot);
    }

    int sumFourDivisors(vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            auto res = check(x);
            if (res.first == 4)
                ans += res.second;
        }

        return ans;
    }
};