C++で数値が別の数値の累乗であるかどうかを判定する方法

この記事では、ある数値が別の数値の累乗として表せるかどうかを判定する方法を解説します。例えば、125 と 5 という2つの数値が与えられた場合、125 が 5 の累乗であれば true を返します。実際、125 = 5³ なので、この場合は true となります。

判定の考え方はシンプルです。基数 x の累乗値を順番に計算していき、目的の数値 y に一致するかどうかを確認します。一致すれば「表せる」、y を超えてしまえば「表せない」と判断できます。

アルゴリズム

手順は以下の擬似コードの通りです。特別なケースとして、x が 1 の場合は y も 1 のときのみ true を返します（1 の累乗は常に 1 だからです）。

isRepresentPower(x, y):
Begin
    if x = 1, then
        if y = 1, return true, otherwise false
    pow := 1
    while pow < y, do
        pow := pow * x
    done
    if pow = y, then
        return true
    return false
End

C++による実装例

上記のアルゴリズムをC++で実装したコードがこちらです。whileループで累乗値を順次計算し、y と一致するかを判定しています。

#include<iostream>
#include<cmath>
using namespace std;
bool isRepresentPower(int x, int y) {
    if (x == 1)
        return (y == 1);
    long int pow = 1;
    while (pow < y)
        pow *= x;
    if(pow == y)
        return true;
    return false;
}
int main() {
    int x = 5, y = 125;
    cout << (isRepresentPower(x, y) ? "Can be represented" : "Cannot be represented");
}

実行結果

基数 5、判定対象 125 の場合、125 = 5³ なので「表せる」という結果が出力されます。

Can be represented

このアルゴリズムの計算量は O(log_x y) であり、累乗値が y を超えるまでループを回すだけなので非常に効率的です。大きな数値を扱う場合はオーバーフローに注意し、必要に応じて long long 型などを使用するとよいでしょう。