Readme

3715.Sum-of-Perfect-Square-Ancestors

本题的关键点在于，如果a与b的乘积是一个完全平方数，那么将a除去属于完全平方数的因子记作aa，将b除去属于完全平方数的因子记作bb，那么aa与bb必须相等。因为此时aa与bb都不含任何重复的质因子，那么aa*bb就不可能再能被开方。

所以我们用dfs探索这棵树的每一条支路，对于沿途所经历的节点x，都把属于完全平方数的因子剥离，只剩下其“非完全平方数因子”sf[nums[x]]放入一个Hash表中。对于dfs过程中的下一个节点i，进行同样的剥离，得到sf[nums[i]]，查看这个数是否已经存在于Hash之中。Hash有多少即意味着节点i的祖先里有多少个节点能与之配对相乘得到完全平方数。

剥离完全平方数的方法：枚举该数的所有质因子，如果此质因子出现过多次，只保留一次。剩下的部分就是“非完全平方数因子”。

为了加快“枚举该数的所有质因子”，我们可以在计算埃氏筛的同时，存储所有数的最小质因子spf[x]。这样对于x的因数分解，我们可以快速找到突破口，即第一个质因子spf[x].