题意

给出一个整数$x$，把x写成$x=a^p$，求$p$最大是多少？

解题思路

我们可以看看$x$ 的分解质因式：

$[x = a_1^{b_1} \times a_2^{b_2} \times \cdots \times a_k^{b_k}]$

则最终结果为$b_1, b_2, \cdots, b_k$的最大公约数。

有以下两个公式： $[a^p \times b^p = (a \times b)^p]$ $[(a^p)^q = a^{p \times q}$]

具体的证明，我也不怎么会，

但可以举个例子，我们假设求 $144$，

$[144 = 2^4 \times 3^2 = (2 \times 3)^2 \times 4 = 12^2]$

想一下，要求最大幂，确实都得满足所有质因子的幂次方。

注意负数，那肯定不能为偶数，把 $2$ 全部取走就行。

标程

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <deque>
#include <queue>
#include <list>

using namespace std;

// C++98 编译器（如GCC）通常支持扩展的 long long 类型
typedef long long ll;

const long N = 70000;
long prime[N] = {0}, num_prime = 0;  // 存储小于N的素数
int isNotPrime[N] = {1, 1};         // 标记非素数（初始0和1非素数）

// 埃拉托斯特尼筛法生成素数表
int Prime() {
    for (long i = 2; i < N; i++) {
        if (!isNotPrime[i]) {
            prime[num_prime++] = i;
        }
        // 筛除当前数的素数倍数
        for (long j = 0; j < num_prime && i * prime[j] < N; j++) {
            isNotPrime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {  // 遇到最小质因子时停止
                break;
            }
        }
    }
    return 0;
}

// 最大公约数计算（递归实现）
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    ll n;
    Prime();  // 预生成素数表

    // 循环处理输入直到EOF（注意：%lld 是GCC对long long的格式符）
    while (scanf("%lld", &n) != EOF) {
        int flag = 0;  // 标记是否为负数
        if (n == 0) break;

        // 处理负数情况
        if (n < 0) {
            n = -n;
            flag = 1;
        }

        int cnt = 0, ans = 0;
        // 遍历素数表分解质因数
        for (int i = 0; i < num_prime && n > 1; i++) {
            cnt = 0;
            while (n % prime[i] == 0) {
                n /= prime[i];
                cnt++;
            }
            ans = gcd(ans, cnt);  // 动态计算最大公约数
        }

        // 剩余未分解的素数（大于N的情况）
        if (n != 1) {
            ans = 1;
        }

        // 负数情况需去除偶数幂次
        if (flag) {
            while (ans % 2 == 0) {
                ans /= 2;
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}