C++でべき乗を判定する方法：Nがaの累乗かどうかをチェックする

数のべき乗（power）とは、ある数を自分自身に何度も掛け合わせた結果のことです。「指数」や「冪」と呼ばれることもあります。

a の b 乗とは、a を b 回掛け合わせることを意味します。例えば、7 の 2 乗（7²、7 の平方とも呼ばれます）は 7 × 7 = 49 という値になります。

べき乗には、覚えておくと便利な基本的な性質がいくつかあります。

• 任意の数の 0 乗は必ず 1 になります。

• 任意の数の 1 乗は、その数自体になります。一度だけ掛けても値は変化しないためです。

• 負のべき乗は除算に相当します。例えば、a^-3 = 1/a³、すなわち (1/a) × (1/a) × (1/a) となります。

それでは、べき乗の概念を活用したプログラミング問題に取り組んでみましょう。

問題の概要

この問題では、2つの整数 N と a が与えられます。求めるのは、「N が a の何乗かに等しいかどうか」の判定です。

具体的な例で理解を深めましょう。

入力：N = 64、a = 2

出力：Yes（64 は 2 の 6 乗であるため）

解法のアプローチ

シンプルかつ効果的な解法は、a を繰り返し掛け合わせていく方法です。a を順番に累乗していき、途中でちょうど N に一致すれば TRUE を返し、N を超えてしまったら FALSE を返します。これにより、余分な計算をせずに効率よく判定できます。

実装例

この解法を実装した C++ プログラムは以下の通りです。

#include <iostream>
using namespace std;
bool isAPowerNumber(int x, long int y) {
    if (x == 1)
        return (y == 1);
    long int power = 1;
    while (power < y)
        power *= x;
    return (power == y);
}
int main() {
    int N = 625 , a = 5;
    if(isAPowerNumber(a, N))
        cout<<N<<" is a power of "<<a;
    else
        cout<<N<<" is not power of "<<a;
    return 0;
}

出力結果

625 is a power of 5

コードの解説

isAPowerNumber 関数では、まず底 x が 1 の場合の特別処理を行います。1 の累乗は常に 1 なので、y が 1 であるときのみ true を返します。その後、変数 power に x を繰り返し掛け合わせ、y 以上になった時点でループを終了します。最後に power と y が一致するかどうかを返すことで、y が x の累乗であるかを正確に判定できます。

この手法の計算量は O(log N) 程度であり、大きな数に対しても高速に動作するのが特徴です。