思路：暴力枚举幂q，然后n开q次幂之后检查一下是否相等和p是否是素数。
/*****************************牛客统测********************************** * 超级素数 * XSH/2017/3/12 *题目描述 *如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就 *称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要 *找出对应的p,q。 * *输入描述 : *输入一个正整数n(2 ≤ n ≤ 10 ^ 18) * *输出描述 : *如果n是一个超级素数幂则输出p, q, 以空格分隔, 行末无空格。 *如果n不是超级素数幂，则输出No * *输入例子: *27 * *输出例子 : *3 3 ************************************************************************/ bool isPrime(long long n) { long long tmp = sqrt(n); for (long long i = 2; i <= tmp; ++i) if (0 == n%i) return false; return true; } long long isPower(long long m, int n) { return (0 == n) ? 1 : isPower(m, n - 1)*m; } void isSuper(long long n) { //方法一： bool flag = true; for (long long i = 2;; ++i) { double tmp = pow(n, 1.0 / i); if (tmp < 2.0) break; if (isPrime((long long)(tmp + 0.1)) && n == isPower(tmp + 0.1, i)) { flag = false; cout << (int)(tmp + 0.1) << " " << i << endl; } } if (flag) cout << "No" << endl; //方法二： //时间复杂度O（log2(N) * sqrt(sqrt(N))），也就是 以2为底N的对数 乘以 N的4分之1次方 //N = p的q次方，显然p最小时q最大，因为最小的素数是2，所以q的上限也就是log2N即log10(n) / log10(2) /*int p, q; int up = log10(n) / log10(2); for (q = 2; q <= up; q++) { p = pow(n, 1.0 / q); //判断p的q次方是否为n且p为素数 if (pow(p, q) == n && isPrime(p)) { cout << p << " " << q << endl;; break; } } if (q > up) cout << "No" << endl;*/ } int main() { long long N; while (cin >> N) isSuper(N); system("pause"); return 0; }
