8041. 完全子集的最大元素和

8041.完全子集的最大元素和

题目描述：

给你一个下标从 1 开始、由 n 个整数组成的数组。

如果一组数字中每对元素的乘积都是一个完全平方数，则称这组数字是一个 完全集 。

下标集 {1, 2, ..., n} 的子集可以表示为 {i1, i2, ..., ik}，我们定义对应该子集的 元素和 为 nums[i1] + nums[i2] + ... + nums[ik] 。

返回下标集 {1, 2, ..., n} 的 完全子集 所能取到的 最大元素和 。

完全平方数是指可以表示为一个整数和其自身相乘的数。

数据范围：

$1\le n \le 10^4; 1\le nums[i] \le 10^9$

题解：

两个数相乘为完全平方数，假设把这两个数分解质因数，那么这两个数的奇数次方的因子都是相同的。也就是说去除偶数次方的因子，剩下的所有数的乘积，二者是相同的。因此可以枚举这个剩下的数。因为是完全子集，其实完全子集的去除偶数次方的剩下的数应该是全都一样。

因此可以枚举剩下的数乘以各种完全平方因子，得到的数都是这个子集中的，然后把它们加起来。

代码：

class Solution
{
public:
    const static int maxn = 1e4 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    long long maximumSum(vector<int> &nums)
    {
        int n = nums.size();
        long long ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            long long sum = 0;
            for(int j = 1; j <= n; ++j)
            {
                if(i * j * j <= n)
                {
                    sum += nums[i * j * j - 1];
                }
                else break;
            }
            ans = max(ans, sum);
        }
        return ans;
    }
};