문제 14
거듭제곱인가?
정수 $N$이 주어졌을 때, $a^b=N$인 $2$ 이상의 정수 $a$, $b$가 존재한다면 Yes를, 그렇지 않다면 No를 출력하는 프로그램을 작성하라.
입력
첫 번째 줄에 테스트케이스의 개수를 의미하는 정수 $T$가 주어진다. $(1 \le T \le 10\,000)$
두 번째 줄부터 $T$개의 줄에 걸쳐 정수 $N$이 주어진다. $(1 \le N \le 10^{18})$
출력
각 테스트케이스마다 $a^b=N$인 $2$ 이상의 정수 $a$, $b$가 존재한다면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
7 1 4 8 9 10 27 28
예제 출력 1
No Yes Yes Yes No Yes No
공식 해설
제곱수와 세제곱 이상의 거듭제곱 나누기
$U=10^{18}$이라 하자. $a^b\le U$에서 $b\ge3$이면 $a\le10^6$이다. 따라서 제곱수는 질의마다 판정하고, 나머지 지수에 해당하는 수를 한 번만 모아 두면 된다.
각 $a=2,3,\cdots,10^6$에 대해 $a^3$에서 시작하여 $a$를 계속 곱하면서 $U$ 이하인 값을 모두 배열에 넣는다. 배열을 정렬하고 중복을 제거한다. 제곱수도 이 배열에 들어갈 수 있지만 그대로 두어도 판정에 영향을 주지 않는다.
질의 $N$이 $1$이면 No이다. 그 밖에는 제곱수이거나 전처리한 배열에 있으면 Yes, 둘 다 아니면 No이다. 지수가 $2$인 경우와 $3$ 이상인 경우를 모두 확인하므로 빠지는 거듭제곱이 없다.
제곱수 판정은 $[1,10^9]$에서 정수 제곱근을 이분 탐색한 뒤 제곱이 $N$과 같은지 비교하면 실수 오차 없이 할 수 있다. 거듭제곱을 늘릴 때는 현재 값 $v$에 대해 $v\le U/a$일 때만 다음 곱을 계산한다.
중복 제거 전 생성한 값의 수를 $G$라 하면 전처리 시간은 $O(10^6+G\log(G+1))$, 공간은 $O(G)$이다. $G=O(U^{1/3}\log U)$이며 질의당 시간은 $O(\log U+\log(G+1))$이다.
구현 · 언어별 풀이
C++ 구현
생성한 거듭제곱을 vector<long long>에 모아 sort와 unique로 중복을 제거한 뒤 binary_search로 찾는다. 다음 곱을 만들기 전에 v <= U / a인지 확인한다. 제곱수 판정도 정수 이분 탐색으로 처리하며, 답이 될 수 없는 $1$은 먼저 제외한다.
C 구현
long long으로 거듭제곱을 생성하며 v <= U / a일 때만 다음 곱을 만든다. 세제곱 이상 후보는 qsort 후 중복 제거하고 이분 탐색한다. 완전제곱 판정은 정수 제곱근 이분 탐색과 나눗셈 비교로 처리한다.
Python 구현
세제곱 이상 후보를 한 번 생성해 정렬·중복 제거한다. bisect_left로 $N$이 들어갈 위치를 찾고, 그 위치가 배열 범위 안에 있으면서 값이 $N$인지 확인한다. 완전제곱은 math.isqrt로 판정한다. float 제곱근을 반올림하면 $10^{18}$ 근처에서 경계가 틀릴 수 있다.
Java 구현
후보와 $U$는 long으로 두고 v <= U / a를 확인한 뒤 곱한다. 후보는 primitive long[]로 모아 정렬·중복 제거한다. 정수 제곱근은 이분 탐색으로 구해 double 오차와 중간 곱 오버플로를 피한다.
Rust 구현
u64 후보를 Vec에 모아 sort_unstable(), dedup()한 뒤 포함 여부를 이분 탐색으로 확인한다. v <= U / a 조건으로 곱을 보호한다. 제곱근도 정수 이분 탐색으로 구해 f64 반올림에 의존하지 않는다.
JavaScript 풀이
$10^{18}$까지의 입력은 토큰 문자열에서 바로 BigInt로 읽는다. BigInt(Number(token))은 이미 반올림한 값을 복구하지 못한다. 세제곱 이상 후보도 BigInt로 곱하고 Set에 저장하면 중복과 포함 여부를 직접 처리할 수 있다.
$2$부터 $10^6$까지 밑을 순회해 세제곱부터 상한 이하의 거듭제곱을 넣는다. BigInt에는 overflow가 없지만 상한을 넘는 후보는 저장하지 않는다. 질의의 제곱수 여부는 $[1,10^9]$에서 정수 제곱근을 이분 탐색하여 확인한다. Math.sqrt(Number(n))의 반올림만 믿지 않는다.
정렬 대신 해시 집합을 사용하므로 후보 생성 수를 $G$라 할 때 전처리는 기대 $O(10^6+G)$, 질의는 제곱수 탐색 $O(\log U)$와 기대 $O(1)$ 포함 검사이며 공간은 $O(G)$이다. $U=10^{18}$이고 $N=1$은 먼저 No로 처리한다.