C++程序计算机领域题目：找到一个数的幂乘积等于另一个数

问题描述

给定两个正整数n,m，找出所有可能的正整数x和k，使得 $x^k=n$ and $x_1^{k_1} \times x_2^{k_2} \times x_3^{k_3}…\times x_n^{k_n}=m$ 其中， $k_i$ 表示x的幂指数， $x_i$ 表示质因数。

解决方案

先考虑求解一个数的幂是否为另一个数的问题，在C++中可以通过循环求幂来解决。

对于一个整数n和非负整数p，根据定义，n^p等于n的p-1次方乘以n，不断循环可以得到快速求解幂指数的递归代码：

int pow(int n, int p){
    if (p == 0) return 1;
    int power = pow(n, p / 2);
    if (p % 2 == 0) return power * power;
    else return power * power * n;
}

在确定一个数的幂为另一个数之后，接下来需要找到这个数的所有质因数，并计算它们的幂指数，最后再求得所有可能的组合。

C++中可以使用STL中的map来处理质因数问题，先从2到n依次进行除法操作，如果能除尽的话，就代表2是n的一个质因数，以此类推，最终就能得到所有的质因数及对应的幂指数：

int n, m;
cin >> n >> m;
map<int, int> factors;
for (int i = 2; i * i <= n; i++){
    while (n % i == 0){
        factors[i]++;
        n /= i;
    }
}
if (n > 1) factors[n]++;
for (int i = 2; i * i <= m; i++){
    while (m % i == 0){
        factors[i]--;
        m /= i;
    }
}
if (m > 1) factors[m]--;

代码中将所有n和m的质因数及对应的幂指数存储在一个map中，并按照如下方式进行遍历，依次取出质因数对应的幂指数：

bool result = true;
for (auto& factor : factors) {
    if (factor.second < 0 || (factor.second > 0 && n == 1)) {
        result = false; 
        break;
    }
}

示例代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>

using namespace std;

int pow(int n, int p){
    if (p == 0) return 1;
    int power = pow(n, p / 2);
    if (p % 2 == 0) return power * power;
    else return power * power * n;
}

int main(){
    int n, m;
    cin >> n >> m;
    map<int, int> factors;
    for (int i = 2; i * i <= n; i++){
        while (n % i == 0){
            factors[i]++;
            n /= i;
        }
    }
    if (n > 1) factors[n]++;
    for (int i = 2; i * i <= m; i++){
        while (m % i == 0){
            factors[i]--;
            m /= i;
        }
    }
    if (m > 1) factors[m]--;
    bool result = true;
    for (auto& factor : factors) {
        if (factor.second < 0 || (factor.second > 0 && n == 1)) {
            result = false; 
            break;
        }
    }
    if (result) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}