문제
lo부터 hi까지의 모든 a와 모든 b에 대해 a^b를 계산합니다. 2^4 = 4^2 = 16처럼 같은 값이 여러 번 나오기도 합니다. 서로 다른 값이 몇 개인지 세세요. 값은 엄청나게 크지만 실제로 계산할 필요는 없습니다. a를 r^k로 나타내되 r 자체는 다른 수의 거듭제곱이 아니도록 하면 a^b = r^(k × b)입니다. 두 거듭제곱은 r이 같고 지수 k × b도 같을 때, 오직 그때만 같습니다.
distinct_powers(lo, hi) 함수를 구현하세요.
입력
lo: 가장 작은 밑이자 지수입니다.
hi: 가장 큰 밑이자 지수입니다.
출력
lo ≤ a ≤ hi, lo ≤ b ≤ hi일 때 a^b의 서로 다른 값의 개수를 반환합니다.
제약 조건
2 ≤ lo ≤ hi ≤ 100
예시
입력:
lo = 2
hi = 4
예상 출력:
expected = 8
입력:
long long lo = 2;
long long hi = 4;
예상 출력:
long long expected = 8;
입력:
long lo = 2;
long hi = 4;
예상 출력:
long expected = 8;
설명
아홉 개의 거듭제곱은 4, 8, 16, 9, 27, 81, 16, 64, 256입니다. 16이 두 번 나오므로 서로 다른 값은 8개입니다.
입력:
lo = 7
hi = 7
예상 출력:
expected = 1
입력:
long long lo = 7;
long long hi = 7;
예상 출력:
long long expected = 1;
입력:
long lo = 7;
long hi = 7;
예상 출력:
long expected = 1;
설명
7^7 하나뿐이므로 1입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
r^k = a가 되는 가장 작은 r과 가장 큰 k를 찾으세요.
힌트 2
a^b는 r^(k × b)와 같으므로 쌍 (r, k × b)로 값을 구별할 수 있습니다.
힌트 3
이 쌍들을 집합에 넣고 개수를 세세요.
예상 복잡도
시간 O((hi − lo)² log hi), 추가 공간 O((hi − lo)²)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.