难度: Medium
给你一个整数数组 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 <= 1041 <= nums[i] <= 105运行时间: 152 ms
内存: 18.0 MB
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
table = {}
res = 0
def FourDivSum(num):
i = 2
while i * i < num:
if num % i == 0:
break
i += 1
if i * i >= num:
return 0
if i ** 3 == num:
return sum([i ** j for j in range(4)])
num = num // i
j = 2
while j * j <= num:
if num % j == 0:
break
j += 1
if j * j > num:
#print([1, i, num, i * num])
return sum([1, i, num, i * num])
return 0
for num in nums:
if num in table:
res += table[num]
continue
table[num] = FourDivSum(num)
res += table[num]
return res
这个题解的核心思路是通过遍历数组中的每个数字，并检查每个数字具有四个因数的情况。对每个数字，它首先尝试找到第一个小于其平方根的因数。如果找到这样的因数，它会尝试确定这个因数和剩余的商是否可以形成四个因数的组合。数学上，一个数字有四个因数的情况通常是它由两个不同的质因数组成（形如 p*q），或它是某个质数的三次方（形如 p^3）。对于每个数字的因数检查，如果符合四因数的条件，则计算这四个因数的和。为了避免重复计算，使用一个哈希表来存储已经计算过的数字及其因数之和。
时间复杂度: O(m*sqrt(n))
空间复杂度: O(m)
class Solution:
def sumFourDivisors(self, nums: List[int]) -> int:
table = {} # used to store the sums of divisors of numbers already checked
res = 0 # the final result sum
def FourDivSum(num):
i = 2
while i * i < num:
if num % i == 0:
break
i += 1
if i * i >= num:
return 0
if i ** 3 == num:
return sum([i ** j for j in range(4)]) # handles the case p^3
num = num // i
j = 2
while j * j <= num:
if num % j == 0:
break
j += 1
if j * j > num:
# handles the case p*q
return sum([1, i, num, i * num])
return 0
for num in nums:
if num in table:
res += table[num] # use cached result
continue
table[num] = FourDivSum(num) # calculate and store the sum of four divisors
res += table[num]
return res
检查一个数字小于其平方根的因数是一种高效的因数查找方法。因为如果一个数n可以被另一个数d整除（即n = d * k），那么d和k中至少有一个必须小于或等于n的平方根。如果两者都大于n的平方根，那么d*k会大于n，这与假设矛盾。因此，只需要检查到平方根就可以了。这样减少了检查的范围，提高了算法效率。
这种分类基于因数的组成原理。对于形如p*q的数字，如果p和q是不同的质数，那么该数字具有的四个因数是1, p, q, pq。这是因为质数除了1和本身没有其他因数。对于形如p^3的数字，如果p是质数，那么它的四个因数是1, p, p^2, p^3。这两种情况都是在特定条件下因数恰好为四个的情况，分别对应两个不同质因数的乘积以及一个质数的三次方。
当数字是某个质数p的三次方时，即形如p^3，其因数是1, p, p^2, 和 p^3。在这里，`i`是这个质数p。因此，`sum([i ** j for j in range(4)])`的计算实际上是在计算1 (即p的0次方), p (即p的1次方), p^2 (即p的2次方), 和 p^3 (即p的3次方)的和。这样确保正确计算了所有的因数和。
当`i * i >= num`时，意味着没有找到小于平方根的因数，因此num是质数或只有1和自身为因数的数字。在这种情况下，num不能有四个因数。返回0表示该数字不符合题目要求的具有四个不同因数的条件，因此在这种情况下不进行进一步的因数求和计算。