C++에서 한 숫자가 다른 숫자의 거듭제곱인지 확인하는 방법

이 글에서는 어떤 숫자가 다른 숫자의 거듭제곱인지 판별하는 방법을 알아보겠습니다. 예를 들어 125와 5라는 두 숫자가 주어졌을 때, 125가 5의 거듭제곱이면 참(true)을 반환해야 합니다. 실제로 125 = 5³이므로 이 경우 결과는 참이 됩니다.

알고리즘

핵심 아이디어는 간단합니다. 밑(base)이 되는 숫자 x를 계속 곱해가면서 목표 값 y에 도달하는지 확인하는 것입니다.

isRepresentPower(x, y):
시작
    만약 x = 1이라면
        y = 1이면 true 반환, 아니면 false 반환
    pow := 1
    pow < y 인 동안 반복
        pow := pow * x
    반복 끝
    만약 pow = y라면
        true 반환
    false 반환
끝

x가 1인 경우를 먼저 처리하는 이유는, 1은 몇 번을 곱하더라도 값이 변하지 않기 때문입니다. 따라서 x가 1일 때는 y 역시 1인 경우에만 참이 됩니다(1 = 1ⁿ).

C++ 구현 예제

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

bool isRepresentPower(int x, int y) {
    // 밑이 1인 경우: y도 1일 때만 거듭제곱 표현 가능
    if (x == 1)
        return (y == 1);

    long int pow = 1;
    while (pow < y)
        pow *= x;

    return (pow == y);
}

int main() {
    int x = 5, y = 125;
    cout << (isRepresentPower(x, y) ? "표현할 수 있음" : "표현할 수 없음");
}

실행 결과

표현할 수 있음

동작 원리 설명

위 코드에서 x = 5, y = 125가 주어지면 다음과 같이 진행됩니다.

처음 pow는 1이고, 반복문을 통해 1 → 5 → 25 → 125로 증가합니다. pow가 125가 되는 순간 y와 같아지므로 반복문이 종료되고, 최종 비교에서 참을 반환하여 "표현할 수 있음"이 출력됩니다.

만약 y가 x의 거듭제곱이 아니라면, 반복문이 종료되었을 때 pow가 y보다 커지게 되어 거짓을 반환하게 됩니다.

시간 복잡도

이 방법의 시간 복잡도는 O(log_xy)입니다. 매 반복마다 pow가 x배씩 증가하기 때문에, 지수 크기만큼만 반복하면 되어 매우 효율적입니다. 또한 오버플로우를 방지하기 위해 pow 변수를 long int로 선언한 점에 유의하세요.