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

この記事では、与えられた数値が a^b（a・b は整数）という累乗の形で表現できるかどうかを判定する方法を解説します。例えば、125 という数値は 5³ と表現できるため「表現可能」です。一方、91 はいかなる整数の累乗としても表現できません。

アルゴリズムの考え方

判定には対数（log）を利用します。底となる候補 i を 2 から順に試し、「i を何乗すると num になるか」を log(num) / log(i) で計算します。この値がほぼ整数であれば、num は i^val と表現できることになります。

isRepresentPower(num):
開始
　　もし num = 1 ならば true を返す
　　i := 2 から i² ≤ num の間、i を 1 ずつ増やしながら以下を繰り返す：
　　　　val := log(num) / log(i)
　　　　もし val − int(val) ＜ 0.0000000001 ならば true を返す
　　繰り返し終了
　　false を返す
終了

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;

bool isRepresentPower(int num) {
    // 1 は常に 1^b と表現できる
    if (num == 1)
        return true;
    // 底 i を 2 から √num まで調べる
    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

コードのポイント

• num = 1 の場合：1 は 1^b として常に表現できるため、即座に true を返します。
• ループ範囲：底 i は 2 から √num まで調べれば十分です。i が平方根を超えると指数が 2 未満になり、意味のある累乗にならないためです。
• 許容誤差：浮動小数点演算には丸め誤差が伴うため、小数部が 0.00000001 未満の場合に「ほぼ整数」とみなしています。これにより誤判定を防ぎます。

このように対数を使うことで、累乗判定を効率的に O(√n) の計算量で行うことができます。