GESP C++二级幂和数问题解析与算法实现

1. GESP C++二级编程题解析：幂和数问题

在GESP（青少年编程能力等级考试）C++二级认证中，幂和数问题是一个典型的算法编程题。这类题目考察考生对循环结构、条件判断和数学运算的综合运用能力。我们先来看题目描述：

题目要求：给定一个正整数n，判断它是否可以表示为m^k的形式，其中m和k都是大于1的整数。如果是，则输出"YES"并给出所有可能的表示方式；否则输出"NO"。

1.1 问题分析与解题思路

幂和数问题的核心在于分解一个数的所有可能的指数表示形式。对于给定的n，我们需要找到所有满足m^k = n的整数对(m,k)，其中m>1且k>1。

解决这个问题的关键在于：

1. 确定k的可能取值范围
2. 对于每个可能的k，检查是否存在整数m使得m^k = n
3. 收集所有满足条件的(m,k)对

注意：k的最大可能值不会超过log₂n，因为2^log₂n = n。这为我们确定了k的上限，避免无限循环。

1.2 算法设计与实现步骤

1.2.1 确定k的范围

k的最小值为2，最大值为floor(log2(n))。在C++中，我们可以使用log函数计算对数：

cpp复制#include <cmath>
int max_k = floor(log(n)/log(2));

1.2.2 检查每个k的可能性

对于每个k从2到max_k，我们需要检查是否存在整数m使得m^k = n。这可以通过以下步骤实现：

1. 计算n的k次方根
2. 检查该方根是否为整数
3. 如果是整数，则记录(m,k)对

1.2.3 完整代码实现

cpp复制#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

void checkPowerNumber(int n) {
    vector<pair<int, int>> results;
    bool found = false;
    
    int max_k = floor(log(n)/log(2));
    
    for(int k=2; k<=max_k; k++) {
        double m = pow(n