LeetCode 1390. 四因数

思路

从1开始遍历到题目范围的因子，将有这个因子的数因子数加1，因数和加上这个因子。
然后遍历nums查表即可。

代码

class Solution {
public:
    const static int l=1e5+5;
    int dp[l+1];
    int cnt[l+1];
    void cal(){
        for(int i=1;i<=l;i++){
            int n=l/i;
            for(int j=1;j<=n;j++){
                int index=i*j;
                dp[index]++,cnt[index]+=i;
            }
        }
    }
    int sumFourDivisors(vector<int>& nums) {
        int res=0;
        cal();
        for(int i=0;i<nums.size();i++)
            if(dp[nums[i]]==4)
                res+=cnt[nums[i]];
        return res;
    }
};

参考

1. https://leetcode-cn.com/problems/four-divisors/ ↩