如何判断正整数是否为平方、立方等幂次方并返回最小底数？

咱们来一步步拆解你提供的C代码，看看它能不能实现「判断大于0的整数是否为平方数、立方数等幂次方数，并返回最小底数」的需求，比如输入64返回2这种场景。

先理清楚你的代码思路 #

1. intpow函数：用递归快速幂的方式计算b^e，逻辑上是对的，快速幂的效率比普通循环要高。
2. check_perfect_power函数：从最大的指数p（32位系统下是32，因为sizeof(int)*8）开始往下遍历，对每个指数p，尝试从底数i=2开始计算i^p，如果等于n就直接返回i；遍历完所有p>2的情况还没找到，就返回-1。

但这段代码存在几个关键问题，没法完全满足需求 #

1. 完全漏掉了平方数的判断 #

你代码里的循环条件是for(p=sizeof(int)*8;p>2;p--)，也就是说只检查了指数>=3的情况（立方及以上），完全忽略了平方数（指数=2）的场景。比如：

• 输入n=4（2²）或者n=9（3²）时，代码会遍历p从32到3，找不到任何匹配的i，最终返回-1，但这些数明明是幂次方数，应该返回对应的最小底数。

2. 整数溢出会导致错误判断 #

intpow用int存储计算结果，当i和p比较大时，i^p会超出32位int的最大值（2147483647），导致溢出，变成负数或者乱码值。比如：

• 输入n=2147483647（int最大值），当i=2、p=31时，2³¹=2147483648，超出int范围后溢出为-2147483648，这时候intpow(2,31) <=n的判断会变成-2147483648 <=2147483647，结果是true，代码会继续判断是否等于n，显然不等，但后续增大i后，计算的i^p会继续溢出，可能导致误判或者无效遍历。

3. 没处理n=1的情况（需求是大于0的整数） #

n=1可以表示为1^e（e>=2），但代码里i从2开始遍历，所以输入1会返回-1。如果需求里n=1需要返回1，这里也得调整。

修正后的代码示例 #

针对上面的问题，我们可以做这些改进：

• 补上指数p=2的判断；
• 用long long做中间计算避免溢出，同时加入溢出检测；
• 优化指数的遍历上限，不用从32开始，而是取log2(n)减少不必要的循环。

#include <stdio.h>
#include <math.h>

// 带溢出检测的快速幂，若溢出或结果超过n，返回n+1
int intpow(int b, int e, int n) {
    long long result = 1;
    long long base = b;
    while (e > 0) {
        if (e & 1) {
            result *= base;
            if (result > n) {
                return n + 1;
            }
        }
        base *= base;
        // 提前判断：如果base已经超过n，且还有更多次方要算，直接返回n+1
        if (base > n && e > 1) {
            return n + 1;
        }
        e >>= 1;
    }
    return (int)result;
}

int check_perfect_power(int n) {
    if (n <= 1) {
        return n == 1 ? 1 : -1;
    }
    
    // 指数的上限：2^max_p <= n < 2^(max_p+1)，不用遍历到32
    int max_p = log2(n);
    for (int p = max_p; p >= 2; p--) {
        for (int i = 2; ; i++) {
            int res = intpow(i, p, n);
            if (res == n) {
                return i;
            }
            if (res > n) {
                break; // 超过n了，没必要继续增大i
            }
        }
    }
    return -1;
}

// 测试用例
int main() {
    printf("%d\n", check_perfect_power(64)); // 输出2，符合需求
    printf("%d\n", check_perfect_power(4));  // 输出2，正确识别平方数
    printf("%d\n", check_perfect_power(9));  // 输出3，正确识别平方数
    printf("%d\n", check_perfect_power(2147483647)); // 输出-1，正确
    printf("%d\n", check_perfect_power(1));  // 输出1，处理n=1的情况
    return 0;
}

验证修正后的逻辑 #

• 输入64：遍历到p=6时，i=2的计算结果等于64，直接返回2，符合需求；
• 输入4：遍历到p=2时，i=2的计算结果等于4，返回2，正确识别平方数；
• 溢出场景：计算i=2、p=31、n=2147483647时，会检测到结果超过n，直接返回n+1，跳出循环，避免错误判断。

内容的提问来源于stack exchange，提问作者heskin vader