1390. 四个约数

Source: Dev.to

Problem Statement

给定一个整数数组 nums，返回数组中所有恰好有四个约数的整数的约数之和。如果数组中不存在这样的整数，返回 0。

Examples

Example 1

Input: nums = [21,4,7]
Output: 32

Explanation:

• 21 有 4 个约数：1, 3, 7, 21
• 4 有 3 个约数：1, 2, 4
• 7 有 2 个约数：1, 7

只有 21 符合条件，其约数之和为 1 + 3 + 7 + 21 = 32。

Example 2

Input: nums = [21,21]
Output: 64

两个元素都是 21，每个贡献 32，总计 64。

Example 3

Input: nums = [1,2,3,4,5]
Output: 0

数组中没有恰好有四个约数的数字。

Constraints

1  4) {
                // More than four divisors – not eligible.
                return 0;
            }
        }
    }

    return ($cnt === 4) ? $sum : 0;
}

// Test cases
echo sumFourDivisors([21,4,7]) . "\n";          // Output: 32
echo sumFourDivisors([21,21]) . "\n";           // Output: 64
echo sumFourDivisors([1,2,3,4,5]) . "\n";       // Output: 0
?>

Solution (PHP)

<?php
function sumFourDivisors(array $nums): int {
    $total = 0;
    foreach ($nums as $num) {
        $total += fourDivisorsSum($num);
    }
    return $total;
}

function fourDivisorsSum(int $n): int {
    $cnt = 0;
    $sum = 0;
    for ($i = 1; $i * $i <= $n; $i++) {
        if ($n % $i === 0) {
            $cnt++;
            $sum += $i;
            $other = intdiv($n, $i);
            if ($other !== $i) {
                $cnt++;
                $sum += $other;
            }
            if ($cnt > 4) {
                // More than four divisors – not eligible.
                return 0;
            }
        }
    }

    return ($cnt === 4) ? $sum : 0;
}

// Test cases
echo sumFourDivisors([21,4,7]) . "\n";          // Output: 32
echo sumFourDivisors([21,21]) . "\n";           // Output: 64
echo sumFourDivisors([1,2,3,4,5]) . "\n";       // Output: 0
?>

Main Algorithm

1. 遍历 输入数组的每个元素。
2. 判断 当前数字是否恰好有四个约数，方法是扫描到其平方根，同时计数并累计约数。
3. 累计 符合条件的数字的约数之和。

Complexity Analysis

• 时间复杂度： O(n × √m)，其中 n 为 nums 的长度，m 为 nums 中的最大值。
• 空间复杂度： O(1) 额外空间（不计入输入数组）。