1390：四因数（1478 分）

力扣第 181 场周赛第 2 题

题目

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。

示例 1：

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

示例 2:

输入: nums = [21,21]
输出: 64

示例 3:

输入: nums = [1,2,3,4,5]
输出: 0

提示：

• 1 <= nums.length <= 104
• 1 <= nums[i] <= 105

分析

预处理每个数的因子个数/和即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

N = 10**5+1
f = [0]*N
g = [0]*N
for i in range(1,N):
    for j in range(i,N,i):
        f[j] += 1
        g[j] += i

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        return sum(g[x] for x in nums if f[x]==4)

1 ms