原文链接: https://leetcode-cn.com/problems/four-divisors

英文原文

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

 

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation: 
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Example 2:

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

Example 3:

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

 

Constraints:

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

中文题目

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数，则返回 0 。

 

示例：

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

 

提示：

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

通过代码

高赞题解

过不了的问题主要出在测试用的83521和2401这两个数上，分别是17和7的四次方。

写法没啥特别的，遍历到根号，计数，但是比赛全程都卡在最后这个巨长的用例上，始终找不到为啥。
这是比赛途中采用的代码：

#include <math.h>

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int res = 0;
        
        for(int i = 0; i < nums.size(); ++i){
            int cnt = 0;
            int sum = 0;
            
            for(int j = 2; j < sqrt(nums[i]); ++j){
                if(nums[i] % j == 0){
                    cnt++;
                    sum += j;
                    sum += nums[i] / j;
                    
                }
                if(cnt > 1) break;
            }
            if(cnt == 1){
                res = res + sum + nums[i] + 1;
            } 
        }
        
        return res;
    }
};

这里我以为j < sqrt(nums[i])而不用等于就可以避免平方根的问题，但是显然忽略了更高阶的四次方情况。

排错方式比较智障，人工二分法测试，找到了83521和2401这两个数，发现其四次方特性。
参考评论区各位前辈代码，把平方判断单独拿出来写：

#include <math.h>

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int res = 0;
        
        for(int i = 0; i < nums.size(); ++i){
            int cnt = 0;
            int sum = 0;
            int sq = sqrt(nums[i]);

            for(int j = 2; j <= sq; ++j){
                if(nums[i] % j == 0){
                    cnt++;
                    sum += j;
                    sum += nums[i] / j;
                    
                }
                if(cnt > 1) break;
            }
            if(cnt == 1 && sq * sq != nums[i]){
                res = res + sum + nums[i] + 1;
            } 
        }
        
        return res;
    }
};

通过~

统计信息

通过次数	提交次数	AC比率
6891	18984	36.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言