雜事、解題紀錄

周賽363。沒想通完全平方數背後真正的意義，真可惜。

題目

輸入長度n的整數陣列nums。

完全平方數指的是一個正整數，可以表示為另個整數的平方。

如果一個整數集合中，任意兩個元素乘積都是完全平方數，則稱為完整的。

索引集合{1, 2, …, n}的一個子集{i1, i2, …, ik}，其元素和定義為：nums[i1] + nums[i2] + … + nums[ik]。

求索引的完整子集的最大元素和。

解法

題目念起來有點繞，反正就是找一坨可以互相組成完全平方數的索引，分到同一組裡面。
同一組的索引i把所有nums[i]加總更新答案。問題是怎麼分組？

一個完全平方數，質因數分解之後，可以拆成數個不同的質因數p，而且他們都是偶數的次方，剛好可以把這些質數平分，變成兩個一樣的數。
反過來說，找兩個索引成績質因數分解後，每個不同的質因數p都是偶數次方，那就是完全平方數。

對於完全平方數來說，只要質因數是偶數次方就行，至於是多少則無所謂。
這其中有更深的意義：一個索引的質因數p若是偶數次方，那他一定可以和另個索引平分，所以乾脆無視p。
實際上會影響索引是否滿足完全平方數的，只有奇數次方的質因數。

例如：

索引i = 600
質因數分解 = 2^3 * 3 * 5^2
對於2^3來說，其中的2^2可以兩人平分，只剩下一個2
3只有一個
5^2也可以平分，沒有剩下
實際只剩下2 * 6 = 6
按照這種方式同樣得到6的都是同一組，例如6, 24, …

簡單來說，就是把索引i質因數分解後，只留下奇數質因數後的乘積。
按照次乘積分組，最後找出總和最大的組就是答案。

質因數分解為O(sqrt(x))。
時間複雜度O(N sqrt(x))。但每份測資都是共用同樣的結果，可以預處理質因數分解，之後每次只要O(N)。
空間複雜度不太好算，反正一定小於O(N)。

@cache
def prime_fact(n):
    prod = 1
    p = 2
    while p*p <= n:
        cnt=0
        while n % p == 0:
            cnt+=1
            n //= p
        if cnt%2==1:
            prod *= p
        p += 1
    return prod * n

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        d=Counter()
        for i,x in enumerate(nums):
            pf=prime_fact(i+1)
            d[pf]+=x
            
        return max(d.values())