完备子集的最大元素和

给你一个下标从 1 开始、由 n 个整数组成的数组。
如果一组数字中每对元素下标的乘积都是一个完全平方数，则称这组数字是一个完全集 。
返回下标集 {1, 2, ..., n} 的 完全子集所能取到的最大元素和

1. 数学方法

这里选择从下而上，类似质数筛的方式进行枚举满足条件的完备集合
思考完全集合具备怎么样的性质，相互乘积都是完全平方数，那他们除以相同的公因数后，得到的集合同样是完备集
懒得证明了，直接枚举基本完备子集[1,4,9,16..]的倍数

class Solution {
public:
    long long maximumSum(vector<int> &nums) {
        long long ans = 0;
        int n = nums.size();
        for (int i = 1; i <= n; i++) {
            long long sum = 0;
            for (int j = 1; i * j * j <= n; j++) {
                sum += nums[i * j * j - 1]; // -1 是因为数组下标从 0 开始
            }
            ans = max(ans, sum);
        }
        return ans;
    }
};