平方剩余核

126 views

平方剩余核

定义

平方剩余核 core(n) 为 n 除去完全平方因子后的剩余结果。

模板

MX = 100_001
core = [0] * MX
for i in range(1, MX):
    if core[i] == 0:
        for j in range(1, isqrt(MX // i) + 1):
            core[i * j * j] = i

复杂度证明

证明1
证明2

例题

leetcode 3715
问题转化：两个数x, y相乘要想是完全平方数 => core(x) == core(y)
接着把树转成一个无向图dfs即可，注意搜索顺序，只能向叶子节点方向搜索

MX = 100_001
core = [0] * MX
for i in range(1, MX):
    if core[i] == 0:
        for j in range(1, isqrt(MX // i) + 1):
            core[i * j * j] = i
class Solution:
    def sumOfAncestors(self, n: int, edges: List[List[int]], nums: List[int]) -> int:
        g = [[] for _ in range(n)]
        for e in edges:
            u = e[0]
            v = e[1]
            g[u].append(v)
            g[v].append(u)
        ans = 0
        from collections import defaultdict
        hp = defaultdict(int)
        def dfs(u, fa):
            nonlocal ans
            ans += hp[core[nums[u]]]
            hp[core[nums[u]]] += 1
            for v in g[u]:
                if v != fa:
                    dfs(v, u)
            hp[core[nums[u]]] -= 1
        dfs(0, -1)
        return ans