预计阅读时间：6 分钟

平方剩余核

数论小道具一件：把每个数的平方因子全部剥掉，剩下的「核」才是判断乘积是否为完全平方数的本体。

先澄清名字：本文的「平方剩余核」指无平方因子核（square-free core，也叫 square-free part），和数论里的「平方剩余」（二次剩余，quadratic residue）是两个不同的概念，不要混淆。

定义

平方剩余核 core(n)（square-free core）：n 除以它的最大完全平方因子后剩下的部分，结果一定不含平方因子。例如 core(12) = 12 / 4 = 3，core(18) = 18 / 9 = 2，core(72) = 72 / 36 = 2，core(7) = 7，core(16) = 1。

模板

筛法写法（按 $i \cdot j^2$ 枚举，不是欧拉线性筛；总复杂度仍是 O(MX)，证明见下一节），一次预处理出 1 到 MX - 1 内所有数的 core：

from math import isqrt

MX = 100_001
core = [0] * MX
for i in range(1, MX):
    if core[i] == 0:
        # i * j * j must stay within the last index MX - 1
        for j in range(1, isqrt((MX - 1) // i) + 1):
            core[i * j * j] = i

外层从小到大扫，每个扫到时仍未被标记（core[i] == 0）的 i 必然自身无平方因子：若 $i = s \cdot k^2$ 且 k > 1，那么更小的 s 在之前已经把 i 标记过了。于是这个 i 就是 $i \cdot j^2$ 这一族数的 core。

内层上界写成 isqrt((MX - 1) // i)，保证 i * j * j 不超过最后一个下标 MX - 1；把 MX 改成别的值也不会越界。

复杂度证明

结论：总复杂度 O(MX)。

每个正整数 n 都能唯一写成 $n = s \cdot k^2$，其中 s 无平方因子（s 就是 core(n)）。内层循环只在外层 i = s、内层 j = k 时写 core[n]，所以每个下标恰好被写一次，内层总写入次数正好是 MX - 1。外层循环本身也是 MX - 1 次，合起来 O(MX)。

换个角度按 j 累加也能得到同样的结论：固定 j 时，满足 $i \cdot j^2 < MX$ 的 i 不超过 $MX / j^2$ 个，所以总次数不超过 $MX \cdot \sum_{j \ge 1} 1/j^2 = MX \cdot \pi^2/6 \approx 1.645 \cdot MX$。下面两张图是这条思路的完整推导：

例题

leetcode 3715

题意：给一棵以 0 为根、n 个节点的无向树（edges 给出 n - 1 条边），节点 i 上有正整数 nums[i]。对每个节点 i（1 到 n - 1），统计它的祖先（i 到根路径上的节点，不含 i 自己）中有多少个 ancestor 满足 nums[i] * nums[ancestor] 是完全平方数，记为 $t_i$，返回所有 $t_i$ 之和。数据范围 $1 \le n \le 10^5$，$1 \le nums[i] \le 10^5$。下面的 x、y 就是一对「节点与其祖先」的 nums 值。

问题转化：$x \cdot y$ 是完全平方数 $\iff$ core(x) = core(y)——两数的平方部分怎么乘都还是平方，起决定作用的只有核。

转化完把树按无向图建出来，从根 dfs：用哈希表维护当前根到节点路径上各 core 的出现次数，进入节点时把路径上同 core 的祖先个数计入答案，回溯时撤销计数。注意搜索方向，只能从根向叶子推进。

from collections import defaultdict
from math import isqrt
from typing import List

MX = 100_001
core = [0] * MX
for i in range(1, MX):
    if core[i] == 0:
        # i * j * j must stay within the last index MX - 1
        for j in range(1, isqrt((MX - 1) // 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 u, v in edges:
            g[u].append(v)
            g[v].append(u)
        ans = 0
        hp = defaultdict(int)
        # iterative DFS: a chain of 1e5 nodes would overflow the default recursion limit
        # stack items: (node, parent, entering); entering=False means undo on the way back
        stack = [(0, -1, True)]
        while stack:
            u, fa, entering = stack.pop()
            c = core[nums[u]]
            if not entering:
                hp[c] -= 1
                continue
            ans += hp[c]
            hp[c] += 1
            stack.append((u, fa, False))
            for v in g[u]:
                if v != fa:
                    stack.append((v, u, True))
        return ans

DFS 用显式栈实现：n 最大 1e5，树可能是一条长链，递归写法在 CPython 默认递归上限（1000）下会抛 RecursionError。每个节点入栈两次，第一次（entering 为 True）计入答案并把自己的 core 计数加一，第二次在它的整棵子树处理完之后弹出，撤销计数，效果和递归回溯相同。

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。