모든 챌린지
쉬움 0명 해결 정답률 0%

서로 다른 거듭제곱

구간 안의 a와 b에 대해 a의 b제곱이 몇 가지 서로 다른 값이 되는지 셉니다.

배우게 될 내용

  • 밑을 가장 작은 근으로 줄일 수 있다
  • 거대한 거듭제곱을 계산하지 않고 비교할 수 있다
  • 집합으로 서로 다른 값을 셀 수 있다

문제

원문 보기 (영어)

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

예시

예시 1
입력:
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개입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.