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

题目链接

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

题目描述

给你一个下标从 $1$ 开始、由 $n$ 个整数组成的数组。你需要从 $nums$ 选择一个 完全集，其中每对元素下标的乘积都是一个 完全平方数，例如选择 $a_i$ 和 $a_j$ ，$i\ast 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\le n=nums.length\le 10^4$
• $1\le nums[i]\le 10^9$

解法：质因数分解 + 数学

如果 $i\ast j$ 是一个 完全平方数，那么 $\frac{i}{f_i}\times \frac{j}{f_j}$ 也是一个完全平方数。($f_i,f_j$ 分别是 $i,j$ 的最大平方因子，即 $f_i,f_j$ 也是完全平方数)。

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

因为 $i\ast j$ 是完全平方数。$i\ast j=f_i\ast \frac{i}{f_i}\ast f_j\ast \frac{j}{f_j}$。

因为 $f_i,f_j$ 也是完全平方数，所以 $\frac{i}{f_i}\times \frac{j}{f_j}$ 剩余的因子都应该是 偶数个，即 $\frac{i}{f_i}\times \frac{j}{f_j}$ 也是一个完全平方数。

举例：$2\times 18$ 是一个完全平方数，$2$ 的最大平方因子为 $1$，$18$ 的最大平方因子是 $9$，$\frac{2}{1}\times \frac{18}{9}=2\times 2=4$ 依旧是一个完全平方数。

两个数 $i,j$，如果 $\frac{i}{f_i}=\frac{j}{f_j}$，那么 $i\ast j$ 就是一个完全平方数。

所以在进行 质因数分解，获取最大平方因子$f_i$时，我们以 $\frac{i}{f_i}$ 分组，同一组内元素两两相乘都是完全平方数。直接遍历获取最大的和返回即可。

时间复杂度：$O(n\times 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;
    }
};