算法leetcode

力扣1390-四因数

字数统计: 855字   |   阅读时长: 4分
, ,

摘要: 力扣 1390，算数基本定理与素数筛

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个数论题，属于算数基本定理的应用，当然本题也可以用枚举的方法解决。

题目

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。

提示：

1
2
1 <= nums.length <= 1e4
1 <= nums[i] <= 1e5

示例 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：枚举 + 试除法

枚举每个数 num，然后通过试除法获取 num 的因数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int result = 0;
        for(int num: nums)
        {
            vector<int> divisors = _solve(num);
            if((int)divisors.size() == 4)
                result += accumulate(divisors.begin(), divisors.end(), 0);
        }
        return result;
    }

private:
    vector<int> _solve(int num)
    {
        vector<int> result;
        for(int i = 1; i * i <= num; ++i)
        {
            int j = num / i;
            if(i * j == num)
            {
                result.push_back(i);
                if(i != j)
                    result.push_back(j);
            }
        }
        return result;
    }
};

算法2：素数筛

算术基本定理: 任何一个大于 1 的自然数 N，如果 N 不为质数，那么 N 可以唯一分解成有限个质数的乘积 $N = P_{1}^{a_{1}}P_{2}^{a_{2}}…P_{k}^{a_{k}}$，称该式为 N 的标准分解式。

感觉恰好 4 个因子的数不会很多，于是就考虑能否将它们都先预处理出来。由 N 的标准分解式，x 的因数个数为 $\prod\limits_{i=1}\limits^{k}(a_{i} + 1)$，若其值为 4，则只有两种可能。

  1. x 只有 1 个质因数，对应的指数为 3
  2. x 有两个质因数，对应指数均为 1

数据范围为 $C$，即要预处理出 $\leq C$ 的所有满足以上两条的数。对于第一条，找到所有 $\leq C^{1/3}$ 的质数，对于第二种情况，找到所有不大于 $C$ 的质数，两两相乘再删掉 $> C$ 的结果。

代码 (C++)

其中 get_primes 为素数筛的代码模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        const int C = 1e5;
        const int C3 = pow(C, (double)1/3);
        vector<int> p1 = get_primes(C);
        int m = p1.size();
        unordered_map<int, int> mapping;
        for(int p: p1)
            if(p <= C3)
                mapping[p * p * p] = 1 + p + p * p + p * p * p;
        for(int i = 1; i < m; ++i)
            for(int j = 0; j < i; ++j)
            {
                if(p1[i] <= C / p1[j] + 1)
                    mapping[p1[i] * p1[j]] = 1 + p1[i] + p1[j] + p1[i] * p1[j];
                else
                    break;
            }
        int ans = 0;
        for(int i: nums)
            if(mapping.count(i) > 0)
                ans += mapping[i];
        return ans;
    }

private:
    vector<int> get_primes(int n) {
        if(n < 2) return {};
        vector<bool> vec(n, true);
        vec[0] = false;
        vec[1] = false;
        for(int i = 2; i * i < n; ++i)
        {
            if(vec[i])
            {
                for(int j = i * i; j < n; j += i)
                    vec[j] = false;
            }
        }
        vector<int> result;
        for(int i = 0; i < n; ++ i)
        {
            bool flag = vec[i];
            if(flag)
                result.push_back(i);
        }
        return result;
    }
};
Share