숫자가 a^b 거듭제곱 형태로 표현 가능한지 확인하는 방법 (C++

문제 개요

하나의 숫자 n이 주어졌을 때, 이 숫자를 어떤 수 a의 거듭제곱, 즉 a^b(a의 b제곱) 형태로 표현할 수 있는지 판별하는 문제입니다.

예를 들어 입력값이 125라면, 125 = 5³으로 나타낼 수 있으므로 a = 5, b = 3이 되고 결과는 참(True)입니다. 반면 10처럼 같은 수의 거듭제곱으로 표현할 수 없는 숫자라면 거짓(False)이 됩니다.

해결 접근 방식

핵심 아이디어는 로그(log) 연산을 활용하는 것입니다. 만약 num = a^b가 성립한다면, 양변에 로그를 취했을 때 log(num) / log(a)의 값은 정확히 정수 b가 되어야 합니다. 따라서 후보 밑 a를 차례대로 대입해 보면서 그 결과가 정수에 가까운지만 확인하면 됩니다.

알고리즘은 다음과 같이 진행됩니다.

num이 1이면 참(True)을 반환합니다. (1 = 1^b로 항상 표현 가능)
i를 2부터 시작하여 i × i ≤ num을 만족하는 동안 1씩 늘려가며 반복합니다.
각 i에 대해 val = log(num) / log(i)를 계산합니다.
val의 소수 부분이 거의 0이라면(허용 오차 이내), num은 i의 거듭제곱이므로 참(True)을 반환합니다.
모든 후보를 확인해도 해당하지 않으면 거짓(False)을 반환합니다.

여기서 반복 범위를 √num까지만 잡는 이유는, 지수 b ≥ 2인 거듭제곱 표현이 존재한다면 밑 a는 반드시 √num 이하이기 때문입니다. 이렇게 하면 시간 복잡도를 O(√n)으로 유지할 수 있습니다.

C++ 구현 예제

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

bool solve(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 << solve(n);
}

파이썬 구현 예제

같은 로직을 파이썬으로도 간단하게 구현할 수 있습니다.

import math

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

    i = 2
    while i * i <= num:
        val = math.log(num) / math.log(i)
        if abs(val - round(val)) < 1e-8:
            return True
        i += 1

    return False

n = 125
print(solve(n))

실행 결과

입력값이 125일 때의 출력 결과는 다음과 같습니다.

입력: 125
출력: 1 (True)

125 = 5³이므로 거듭제곱 형태로 표현 가능하다는 의미의 참(True)이 출력됩니다.

구현 시 주의 사항