Leetcode.2862 完全子集的最大元素和

题目链接

Leetcode.2862 完全子集的最大元素和 rating : 2292

题目描述

给你一个下标从

1

1

1 开始、由

n

n

n 个整数组成的数组。你需要从

n

u

m

s

nums

nums 选择一个 完全集，其中每对元素下标的乘积都是一个 完全平方数，例如选择

a

i

a_i

ai​ 和

a

j

a_j

aj​ ，

i

∗

j

i * j

i∗j 一定是完全平方数。

返回 完全子集 所能取到的 最大元素和 。

示例1：

输入：nums = [8,7,3,5,7,2,4,9]
输出：16
解释：
我们选择下标为 2 和 8 的元素，并且 1 * 4 是一个完全平方数。

示例2：

输入：nums = [8,10,3,8,1,13,7,9,4]
输出：20
解释：
我们选择下标为 1, 4, 9 的元素。1 * 4, 1 * 9, 4 * 9 是完全平方数。

提示：

• 1

  ≤

  n

  =

  n

  u

  m

  s

  .

  l

  e

  n

  g

  t

  h

  ≤

  1

  0

  4

  1 \leq n = nums.length \leq 10^4

  1≤n=nums.length≤104

• 1

  ≤

  n

  u

  m

  s

  [

  i

  ]

  ≤

  1

  0

  9

  1 \leq nums[i] \leq 10^9

  1≤nums[i]≤109

解法：质因数分解 + 数学

如果

i

∗

j

i * j

i∗j 是一个 完全平方数，那么

i

f

i

×

j

f

j

\frac{i}{f_i} imes \frac{j}{f_j}

fi​i​×fj​j​ 也是一个完全平方数。(

f

i

,

f

j

f_i,f_j

fi​,fj​ 分别是

i

,

j

i,j

i,j 的最大平方因子，即

f

i

,

f

j

f_i,f_j

fi​,fj​ 也是完全平方数)。

证明过程：
如果一个数是完全平方数，那么它的每一个质因子都应该是偶数个。

因为

i

∗

j

i * j

i∗j 是完全平方数。

i

∗

j

=

f

i

∗

i

f

i

∗

f

j

∗

j

f

j

i * j =f_i * \frac{i}{f_i} *f_j* \frac{j}{f_j}

i∗j=fi​∗fi​i​∗fj​∗fj​j​。

因为

f

i

,

f

j

f_i,f_j

fi​,fj​ 也是完全平方数，所以

i

f

i

×

j

f

j

\frac{i}{f_i} imes \frac{j}{f_j}

fi​i​×fj​j​ 剩余的因子都应该是 偶数个，即

i

f

i

×

j

f

j

\frac{i}{f_i} imes \frac{j}{f_j}

fi​i​×fj​j​ 也是一个完全平方数。

举例：

2

×

18

2 imes 18

2×18 是一个完全平方数，

2

2

2 的最大平方因子为

1

1

1，

18

18

18 的最大平方因子是

9

9

9，

2

1

×

18

9

=

2

×

2

=

4

\frac{2}{1} imes \frac{18}{9} = 2 imes 2 = 4

12​×918​=2×2=4 依旧是一个完全平方数。

两个数

i

,

j

i,j

i,j，如果

i

f

i

=

j

f

j

\frac{i}{f_i} = \frac{j}{f_j}

fi​i​=fj​j​，那么

i

∗

j

i *j

i∗j 就是一个完全平方数。

所以在进行 质因数分解，获取最大平方因子

f

i

f_i

fi​时，我们以

i

f

i

\frac{i}{f_i}

fi​i​ 分组，同一组内元素两两相乘都是完全平方数。直接遍历获取最大的和返回即可。

时间复杂度：

O

(

n

×

l

o

g

n

)

O(n imes logn)

O(n×logn)

C++代码：

using LL = long long;

class Solution {
public:
    long long maximumSum(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int,LL> cnt;

        for(int i = 1;i <= n;i++)
        {
            auto x = i;
            int f = 1;

            for(int d = 2;d <= x / d;d++)
            {
                if(x % d == 0)
                {
                    int k = 0, s = 1;
                while(x % d == 0)
                {
                    x /= d;
                    s *= d;
                    k++;
                }
                //如果k是奇数 需要去掉一个
                //比如 s = 2 * 2 * 2, 由于我们是要求最大平方因子, 所以只需要偶数个, 即 2 * 2 
                if(k & 1) s /= d;
                f *= s;
                }
            }
            //按 i / fi 分组记录记录元素和
            cnt[i / f] += nums[i - 1];
        }

        LL ans = 0;
        for(auto [k, v]:cnt)
        {
            ans = max(ans, v);
        }

        return ans;
    }
};