Readme

2862.Maximum-Element-Sum-of-a-Complete-Subset-of-Indices

我们分析一下“任意两个下标i与j的乘积是完全平方数”的含义。我们将i分解为i=a*x^2，其中x^2是i里包含的最大平方因子。同理，分解j=b*y^2。为了使得i*j依然是平方数，那么必然要求a==b. 同理，与{i,j}属于同一个集合里的其他下标元素，必然也必须能分解为a*z^2的形式。

所以为了最大化这个集合（不仅指集合元素的数目，也指element-sum），集合元素里的那些“最大平方因子”必然是1^2, 2^2, 3^3, 4^2 ... 直至n。然后我们再穷举a=1,2,3.... 就可以构造出所有可能的最优集合，即

1*1, 1*4，1*9, 1*16, ...

2*1, 2*4，2*9, 2*16, ...

3*1, 3*4，3*9, 3*16, ...

直至集合最小元素的上限是n。

那么我们穷举这些元素的时间复杂度是多少呢？对于*1而言，我们穷举了n次。对于*4而言，我们穷举了n/4次。对于*9而言，我们穷举了n/9次。所以总的穷举数目为n/1 + n/4 + n/9 + ...，它是和小于2n的序列。故总的时间复杂度是o(N).