求助一个数论问题

给定一个数 $x$，$(2\le x \le 10^{18})$。把 $x$ 表示成 $k^n$，且 $k \ne a^b$，其中 $k$，$n$，$a$，$b$ 为正整数。

允许 $O(n \log n)$ 以内的预处理，时间复杂度可以做到多少？