平方剩余核
定义
平方剩余核 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
复杂度证明
例题
leetcode 3715
问题转化：两个数x, y相乘要想是完全平方数 => core(x) == core(y)
接着把树转成一个无向图dfs即可，注意搜索顺序，只