质因数分解上的势能分析：AGC003D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132153999

https://www.luogu.com.cn/problem/AT_agc003_d

题目问是否存在立方，值域范围 $1e10$ ，所以很明显类似根号类的题，进行 $^3\sqrt{}$ 分解个质因数。

二分图点对的性质很明显，但很容易忽略它在接下来分析中的作用。

此时剩下最多剩下2个质数，其实分类讨论一下即可。

对于 $p\times q$ ，不可能存在 $p^2\times q^2$ ，所以不可能形成点对。

剩下只有 $p$ 和 $p^2$ 的情况， $p^2$ 一开始肯定认为拿个 sqrt 看看能不能分出来。但如何判断剩下的属于 $p$ 还是 $p\times q$

考虑回到题目，啥时候有贡献。 $p\ge 1e5$ 时显然是不会 $p^2$ ，然后缩小范围至 $3000<p\le1e5$ ，这个范围内显然不存在 $p\times q$

对于此类题，很容易分析出就是靠这类类似大大小小的性质类分析，关键点是要先分类讨论，考虑此时行不行，能不能在细分，细分下去是否能区分。

可以理解成一种质因数分解上的势能分析