超级素数幂解题报告

如果从p进行枚举，则 p∈[2,n√] ，时间复杂度较高，会超时。 如果从q进行枚举，则 q∈[2,log2n] ，时间复杂度较低，可以AC。 下面给出在Java下的代码。

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { long n = in.nextLong(); long q = 2, ceil = (long) (Math.log10(n) / Math.log10(2)); //ceil表示q的枚举上阶 long p = 0; while (q <= ceil) { p = (long) Math.pow(n, 1.0 / q); if (Math.pow(p, q) == n) { if (isPrime(p)) break; } q++; } if (q <= ceil) System.out.println(p + " " + q); else System.out.println("No"); } } private static boolean isPrime(long p) { //判定p是否是素数 if (p < 2) return false; long t = (long) Math.sqrt(p); for (int i = 2; i <= t; i++) { if (p % i == 0) return false; } return true; } }