LeetCode 1390. 四因数

1. 题目

给你一个整数数组 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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/four-divisors 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 直接模拟从2到 n/2,当n很大的时候很耗时
class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int sum = 0;
        pair<bool,int> p;
        for(int i = 0; i < nums.size(); ++i)
        {
        	p = isfour(nums[i]);
            if(p.first)
                sum += p.second;
        }
        return sum;
    }

    pair<bool, int> isfour(int &n)
    {
    	if(n == 1)
    		return {false, 0};
    	int count = 2;
    	int divs = 1+n;
    	for(int i = 2; i <= n/2; ++i)
    	{
    		if(n%i == 0)
    		{
    			count++;
    			divs += i;
            }
    		if(count > 4)
    			return {false,0};
    	}
    	return {count==4,divs};
    }
};
  • 由于因数成对出现,所以从2遍历到 n\sqrt{n}n​ 即可
  • 注意一对因数是相同的情况
class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int sum = 0;
        pair<bool,int> p;
        for(int i = 0; i < nums.size(); ++i)
        {
        	p = isfour(nums[i]);
            if(p.first)
                sum += p.second;
        }
        return sum;
    }

    pair<bool, int> isfour(int &n)
    {
    	if(n == 1)
    		return {false, 0};
    	int count = 2;
    	int divs = 1+n;
    	for(int i = 2; i <= sqrt(n); ++i)
    	{
    		if(n%i == 0)
    		{
                if(i != n/i)
    			{
                    count += 2;
    			    divs += i+n/i;
                }
                else
                {
                    count += 1;
                    divs += i;
                }
            }
    		if(count > 4)
    			return {false,0};
    	}
    	return {count==4,divs};
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 347. 前 K 个高频元素(哈希/优先队列)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/top-k-frequent-elements 著作...

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • Leetcode 870. Advantage Shuffle

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • loj#2312. 「HAOI2017」八纵八横(线性基 线段树分治)

    attack
  • 洛谷P4165 [SCOI2007]组队(排序 堆)

    \[A H_i + B S_i \leqslant C + AminH + BminS\]

    attack
  • 第八届福建省大学生程序设计竞赛 | FZU2280 Magic

    Kim is a magician, he can use n kinds of magic, number from 1 to n. We use strin...

    ACM算法日常
  • loj#6436. 「PKUSC2018」神仙的游戏(生成函数)

    我们考虑枚举一个长度len。有一个结论是如果我们按N - len的余数分类,若同一组内的全为0或全为1(?不算),那么存在一个长度为len的border。

    attack
  • 位操作运算有什么奇技淫巧?(附源码)

    比如说16位二进制数A:1001 1001 1001 1000,如果来你想获A的哪一位的值,就把数字B:0000 0000 0000 0000的那一位设置为1.

    刘盼
  • 【hihocoder 1424】 Asa's Chess Problem(有源汇上下界网络流)

    饶文津

扫码关注云+社区

领取腾讯云代金券