C++で数値がx^y（累乗）として表現できるかどうかを判定する方法

この記事では、ある数値が x^y のような累乗の形で表現できるかどうかを判定する方法を解説します。例えば、125 という数値は 5³ と表現できます。一方、91 のような数値は、いかなる整数の累乗としても表現できません。

アルゴリズムの考え方

判定の基本的なアイデアは次のとおりです。底となる候補 i を 2 から順に試し、log(num) / log(i) を計算します。この結果がほぼ整数になれば、num は i の累乗として表せることになります。

isRepresentPower(num):
Begin
    if num = 1, then return true
    for i := 2, i*i <= num, increase i by 1, do
        val := log(num)/log(i)
        if val - int(val) < 0.0000000001, then return true
    done
    return false
End

ポイント

• 1 は常に 1^y として表現できるため、特別扱いして true を返します。
• ループは i * i <= num までで十分です。それ以上の底では指数が 1 より小さくなり、意味のある累乗になりません。
• 浮動小数点演算には誤差が伴うため、小数部が極めて小さい場合（ここでは 0.00000001 未満）は整数とみなして判定します。

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;
bool isRepresentPower(int num) {
    if (num == 1)
        return true;
    for (int i = 2; i * i <= num; i++) {
        double val = log(num) / log(i);
        if ((val - (int)val) < 0.00000001)
            return true;
    }
    return false;
}
int main() {
    int n = 125;
    cout << (isRepresentPower(n) ? "Can be represented" : "Cannot be represented");
}

実行結果

Can be represented

まとめ

この手法では、対数を使って各候補の底に対する指数を求め、それが整数に近いかどうかで判定を行います。計算量は O(√n) 程度に抑えられるため、比較的大きな数値でも効率的に処理できます。ただし、浮動小数点の誤差を考慮した閾値の設定が重要になる点には注意が必要です。