AGC003D Anticube

比较智慧

比较显然是事实是分解完质因数后幂次 $\bmod 3$ ，完全立方数要求所有质因子幂次之和为三的倍数，这样我们把处理过的幂次记录下来，判断一下相冲突的组哪个比较多就拿哪个

$10^{10}$ 级别的因子分解虽然可以大力 Pollard’s rho，但是应该没人写这个玩意

我们考虑因为因子幂次 $\bmod 3$ ，所以对于 $x$ 先除去 $\sqrt[3]{10^{10}}$ 以内的因子，剩下的肯定是 $pq,p^2,p$ 三者之一

如果这个数 $\ge10^5$ 是 $p$ 已经没意义了，因为对应的 $p^2$大于 $10^{10}$ $pq$ 同理

而如果这个数字不到 $10^5$ 那么不可能为 $p^2,pq$ 的形式，因为这样就有小于 $\sqrt[3]{10^{10}}$ 的因子

综上仅需判断是否平方数即可

不愧是智慧，完全想不到分类讨论只会大力PR

Asusetic eru quionours