预计阅读时间：3 分钟
平方剩余核
数论小道具一件：把每个数的平方因子全部剥掉，剩下的「核」才是判断乘积是否为完全平方数的本体。
定义
平方剩余核 core(n)（square-free core）：n 除去所有完全平方因子后剩下的部分。
模板
线性筛的写法，一次预处理出值域内所有数的 core：
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
外层扫到的第一个未被标记的 i 必然自身无平方因子，它就是 $i \cdot j^2$ 这一族数的 core。
复杂度证明
例题
leetcode 3715
问题转化：$x \cdot y$ 是完全平方数 $\iff$ core(x) = core(y)——两数的平方部分怎么乘都还是平方，起决定作用的只有核。
转化完把树按无向图建出来，从根 dfs：用哈希表维护当前根到节点路径上各 core 的出现次数，进入节点时把路径上同 core 的祖先个数计入答案，回溯时撤销计数。注意搜索方向，只能从根向叶子推进。
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
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。