次幂次幂次幂！题解

先思考这个问题：判断一个数是否为某个数的平方该怎么做？
可行的方法有两种：1是求floor(sqrt())的平方是否为原数，2是枚举因子，将因子的平方标记。
这两种方法一种是O(1)的，一种是需要O(maxnum^(1/2))的时间预处理，以及需要这么大的空间存答案。
同样，判断一个数是否为某个数的三次方该怎么做？
可行的方法有两种：1是求floor(三次方根)的立方是否为原数，2是枚举因子，将因子的立方标记。
这两种方法一种是O(1)的，一种需要O(maxnum^(1/3))的时间预处理，以及需要这么大的空间存答案。
接下来就类推了，我们来计算一下两种方法的总复杂度：

第一种方法，首先对于每个数，我们需要枚举可能的次数，然后进行验证，这个可能的次数我们设为z，底数为d，首先z肯定是一个质数，这样d^z就是指数最小的状况，否则如果z=pq(p,q都不是1)，那么d^z会被分解为(d^p)^q，显然这里p和q会更小。这里我们需要枚举的最大指数是47,比它小的质数有14个。
那么复杂度是O(14n*log(z))的，但我并不想放这种方法过，显然有更优秀的做法。

第二种方法，枚举因子，然后获取它们的次方并求出所有答案。
预处理复杂度是O(maxnum^(1/2)+maxnum^(1/3)+......+maxnum^(1/48))的，这个预处理的上界，通过放缩可以知道，它是不大于O(2maxnum^(1/2))的。
但是依旧很大...而且说明答案的数量也是这个级别，如何存下并实现快速判断是个问题。
存下并快速判断可以使用map，但是map自带一个log...
unordered_map似乎更快，也可以写哈希，但是以上还是过不了。
因此我们可以把平方和其他次方分开，平方单独判断，这样一来，预处理复杂度便成立maxnum的立方根级别，10^5左右，答案的可能性也变成这个级别了，接下来使用unordered_map或哈希就完美地解决了问题。复杂度是O(maxnum^(1/3)+n*？)这里的问号有可能是map的log(大概过不了)，也有可能的unordered_map的常数，也有可能是哈希的常数，哈希效率因人而异，我没有刻意去卡，应该表现不错。