2 ≤ a ≤ 5 이고, 2 ≤ b ≤ 5 인 두 정수 a, b로 만들 수 있는 ab의 모든 조합을 구하면 다음과 같습니다.
22=4, 23=8, 24=16, 25=32, 32=9, 33=27, 34=81, 35=243, 42=16, 43=64, 44=256, 45=1024, 52=25, 53=125, 54=625, 55=3125
여기서 중복된 것을 빼고, 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다.
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
그러면, 2 ≤ a ≤ 100이고, 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 ab는 중복을 제외하면 모두 몇 개 입니까?
http://euler.synap.co.kr/prob_detail.php?id=29
접근
일련의 값에 대해서 가장 빠르게 중복을 제거하는 방법 중 하나는 set()를 사용하는 것이다. 2~100 사이의 수에 대해서 중복 루프를 돌면서 xy를 집합에 추가한 후 최종적으로 중복이 제거된 집합의 원소 수를 세면 된다.
%%time
a = set(x**y for x in range(2, 101) for y in range(2, 101))
print(len(a))지수법칙을 활용하기
큰 수를 지원하지 않는 언어를 사용하거나, 혹은 이렇게 큰 수를 사용하는 것이 반칙같다는 느낌이 든다면 조금 두뇌를 더 회전시켜 보자. xy를 직접 계산하지 않고 밑과 지수로 나누어서 (x, y)로 표현하자. 그리고 이번에는 86을 밑과 지수의 순서쌍으로 표현하는 방법을 생각해보자.
\begin{align}
8^6 &= (2^3)^6 \\
&= 2^{18}
\end{align}즉 순서쌍으로 표현한 (8, 6)은 (23, 6)이므로 지수법칙에 의해 (2, 18)이 되는 것을 알 수 있다. 따라서 밑을 더 작은 수의 거듭제곱으로 교체한다면 이 방식으로 전체 값을 계산하지 않아도 같은 수를 판별할 수 있다. 문제의 조건에서 a, b는 모두 2와 100사이의 수이고, 27 > 100 이므로 a는 더 작은 수 k의 제곱에서 6승 사이의 수와 같은지 확인하면 된다. 또한 더 작은 수 k는 a의 제곱근 이하의 수만 확인하면 될 것 같다.
def transform(a: int, b: int) -> tuple[int, int]:
for k in range(2, int(a**.5+1.5)):
for i in range(2, 7):
if k**i == a:
return (k, b * k)
elif k > a:
break
return (a, b)
print(transform(8, 6))
# (2, 18)
ns = set(transform(a, b) for a in range(2, 101) for b in range(2, 101))
print(len(ns))