프로젝트 오일러 029

문제

29번 문제

2 ≤ <var>a</var> ≤ 100 이고 2 ≤ <var>b</var> ≤ 100인 <var>a</var>, <var>b</var>로 만들 수 있는 <var>a</var>^<var>b</var>의 개수

사이냅소프트

너무 쉬움 주의

100의 100승과 같은 큰 수 때문에 한 때 이것은 어려운 문제였을 수 있겠으나, 더 이상은 어렵지 않습니다.

print(len(set(x**y for x in range(2, 101) for y in range(2,101))))

지수법칙

너무 허무하게 지나갈 수는 없으니, 다른 방법으로도 접근해보겠습니다. 지수로 이루어지는 수들을 튜플의 형식으로 써 보는 겁니다. 예를 들어 8⁷ 을 (8, 7) 이라고 쓰는 것입니다. 그런데 8은 2의 세제곱(2³)이므로, (2³, 7)이고 지수 법칙에 의해 (2, 21)과 같음을 알 수 있습니다. 이런 식으로 밑이 다른 수의 거듭제곱이면 카운트 하지 않는 것이죠.

a, b의 범위는 각각 2∙∙∙100의 범위이기 때문에 검사해야 하는 범위는 한정적입니다. 특히 2⁷ 까지만 100보다 작기 때문에, 2~10까지 범위에서 7제곱으로 표현되는지를 검사하거나 로그를 이용해서 계산할 수도 있습니다.

from math import log

def lower_base(a, b):
    for i in range(2, 11):
        if i >= a:
            break
        j = int(log(a, i))
        if i ** j == a:
            return (i, b * j)
    return (a, b)

xs = set(lower_base(x, y) for x in range(2, 101) for y in range(2,101))
print(len(xs))

큰 수의 지수 계산

큰 수의 곱셉을 이용하면 지수 계산도 할 수 있습니다. 어쩌면 이 문제의 출제 의도는 큰 수의 지수 계산을 사용하라는 것인지도 모르겠습니다. 큰 수의 곱셈 구현도 성능이 썩 나쁘지는 않습니다만, 지수 계산은 다음과 같은 재귀적인 방법으로 횟수를 줄일 수 있습니다.

def s_pow(x: list[int], y: int) -> list[int]:
    if y == 0:
        return [1]
    if y == 1:
        return x
    w = s_pow(x, y // 2)
    z = s_multi(w, w)

    if y % 2 == 0:
        return z 
    return s_multi(z, x)