题目

给你一个整数数组 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 <= 10^4
1 <= nums[i] <= 10^5

解题思路

题目的核心在于快速判断一个数是否有且仅有 4 个因数，并求和。

1. 数学直觉

一个整数 $x$ 的因数总是成对出现的。如果 $i$ 是 $x$ 的因数，那么 $x/i$ 也是 $x$ 的因数。

例如 $x=21$，因数对为 $(1, 21)$ 和 $(3, 7)$。共 4 个。
例如 $x=4$，因数对为 $(1, 4)$ 和 $(2, 2)$。注意 $2$ 重复了，所以只有 3 个因数。

要让一个数恰好有 4 个因数，通常有两种情况（虽解题时不强制要求知道，但有助于理解）：

该数是两个不同质数的乘积（$p_1 \times p_2$），如 $21 = 3 \times 7$（因数为 $1, p_1, p_2, p_1p_2$）。
该数是某个质数的立方（$p^3$），如 $8 = 2^3$（因数为 $1, 2, 4, 8$）。
- 注：完全平方数（如 $4, 9, 16$）通常有奇数个因数，除非它是质数的立方。

2. 算法流程

由于 $nums[i]$ 最大值为 $10^5$，我们不能遍历 $1$ 到 $num$ 去找因数（那样太慢）。最通用的优化方法是只遍历到 $\sqrt{num}$。

对于数组中的每一个数字 num：

初始化 count（因数个数）为 0，sum（因数之和）为 0。
从 $i = 1$ 遍历到 $\lfloor\sqrt{num}\rfloor$：
- 如果 $i$ 能整除 $num$（即 num % i == 0）：
  - 情况 A（不成对）： 如果 $i^2 = num$（即 $i$ 和 $num/i$ 相等），这是一个完全平方数。count 加 1，sum 加 $i$。
  - 情况 B（成对）： 如果 $i^2 \neq num$，说明找到两个不同的因数 $i$ 和 $num/i$。count 加 2，sum 加上 $i + num/i$。
剪枝优化： 如果在遍历过程中 count 已经超过 4，直接停止该数的计算（它不符合要求）。
遍历结束后，检查 count 是否严格等于 4。如果是，将该数的 sum 加入总结果。

具体代码

func sumFourDivisors(nums []int) int {
    ans := 0
    for _, num := range nums {
        // 剪枝：小于6的数（1,2,3,4,5）因数个数肯定不足4个或不等于4个
        // 4 的因数是 1, 2, 4 (3个)
        if num < 6 {
            continue
        }

        count := 0
        sum := 0
        
        // 遍历到 sqrt(num)
        for i := 1; i*i <= num; i++ {
            if num%i == 0 {
                if i*i == num {
                    // 完全平方数，因数只加 1 个 (例如 4 的因数 2)
                    // 注意：完全平方数的因数总个数其实是奇数，永远不可能等于 4
                    // 所以这一步其实注定了它最后通不过 count == 4 的检查
                    count++
                    sum += i
                } else {
                    // 成对出现的因数
                    count += 2
                    sum += i + num/i
                }
                
                // 剪枝：一旦超过 4 个，立刻停止，处理下一个数
                if count > 4 {
                    break
                }
            }
        }
        
        // 只有恰好 4 个因数才计入总和
        if count == 4 {
            ans += sum
        }
    }
    return ans
}

1390. 四因数

beautifulremi

题目

解题思路

1. 数学直觉

2. 算法流程

具体代码