超级素数幂

问题描述

如果一个数字能表示为p^q(表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。

输入描述

输入一个正整数n(2 ≤ n ≤ 10^18)

输出描述

如果n是一个超级素数幂则输出p,q,以空格分隔,行末无空格。
如果n不是超级素数幂，则输出No

输入例子

27

输出例子

3 3

分析

n = p^q，n=[2, 10^18]，显然p的范围很大，没法枚举；q作为指数项，最大值为logn，是可以枚举。所以我们可以穷举q，反求p，判断p是不是整数和素数，如果是整数则表示找到一组解了。

note

1. 按照题目的说法，超级素数幂的p q对是唯一的；
2. 如何找到合适的可枚举空间是解决问题的关键。

代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

bool isPrime(long long l)
{
    for (long long i = 2; i <= sqrt(l); i++)
        if (l % i == 0) return false;
    return true;
}

int main()
{
    long long n;
    scanf("%lld", &n);

    long long m = log(n) / log(2);
    for (int i = 2; i <= m; i++)
    {
        double d = pow(n, 1.0 / i);
        long long l = (long long)d;
        if (abs(d - l) > 0.0001)
            continue;

        if (isPrime(l))
        {
            printf("%lld %d\n", l, i);
            return 0;
        }
    }

    printf("No\n");

    return 0;
}