Pythonで数値がa^bの形で表現できるかどうかを判定する方法

問題概要

ある数値 n が与えられたとき、その数値を a^b（aのb乗）の形で表現できるかどうかを判定する問題です。

例えば、入力が 125 の場合を見てみましょう。125 = 5^3 と表せるため、出力は True となります（このとき a = 5、b = 3）。

解き方のアプローチ

この問題は、対数（ログ）を利用することで効率的に解くことができます。手順は以下の通りです。

• num が 1 の場合は true を返します（1 = 1^b と常に表現できるため）。
• i を 2 から始め、「i × i ≤ num」が成り立つ間ループを回します。
• 各 i について val = log(num) / log(i) を計算します。これは「num が i の何乗に相当するか」を表す値です。
• val の小数部分がほぼ 0（許容誤差 1e-8 未満）であれば、num は i の整数乗で表せることになるので true を返します。
• ループが終了しても該当する i が見つからなければ false を返します。

ここで重要なのが浮動小数点数の誤差です。対数の計算結果は厳密な整数になるとは限らないため、round() との差分が十分小さいかどうかで判定するのが安全です。

Pythonでの実装例

import math

def solve(num):
    if num == 1:
        return True

    i = 2
    while i * i <= num:
        val = math.log(num) / math.log(i)
        # 浮動小数点誤差を考慮し、valがほぼ整数かどうかを判定
        if abs(val - round(val)) < 1e-8:
            return True
        i += 1

    return False


n = 125
print(solve(n))

入力

125

出力

True

処理の流れを確認

n = 125 の場合、まず i = 2 では log(125) / log(2) ≈ 6.97 となり整数ではないためスキップされます。次に i = 3 でも同様に不成立ですが、i = 5 に到達すると log(125) / log(5) = 3.0 となり、ほぼ整数であることが判定できるため True が返されます。

計算量

ループは i × i ≤ num の範囲で回るため、時間計算量は O(√n) となります。対数計算は定数時間で行えるため、大きな数値に対しても高速に動作します。

補足：浮動小数点誤差を避けたい場合

より厳密に判定したい場合は、対数に頼らず整数演算だけで累乗を試す方法もあります。たとえば、底 a を固定した状態で a, a², a³, … と掛け算を繰り返し、num に一致するかを確認すれば、誤差の心配なく正確に判定できます。ただし、対数を使う方法の方がコードが簡潔で、多くの場面では十分実用的です。