백준 13010 h(n)

문제

https://www.acmicpc.net/problem/13010

13010번: h(n)

 

풀이

2^60 > 10^18이므로 n에 상관없이 d(n)은 60이하여야한다.

X^Y = N을 만족하는 X, Y pair를 찾아야한다.

약수의 개수가 최소 2개이상이므로,(1은 입력으로 들어오지 않는다) Y를 2부터 60까지 순회하며 만족하는 X를 찾는다.

left = 1;
right = N;
while (left <= right){
	mid = (left + right) / 2
	num = pow(mid,Y)
	if (num == N) {return mid;}
	else if (num < N) {mid = left + 1;}
	else {mid = right - 1;}
	}
// 만족하는 X가 없다
return -1;

 

이분 탐색을 이용해 X를 찾아줄 수 있다.

하지만 문제는 pow이다. mid랑 Y가 크다면 감당할 수 없는 큰 수를 리턴할 것이다.

r = 1;
for (int i =0;i<Y;i++){
	r = r * mid
    if (r > INF){break;}
}
return r;

수가 너무 커지면 break해준다.

N제한이 10^18이므로 r이 10^18보다 커진다면 더 제곱할 필요가 없어진다. (INF는 10^18보다 조금 더 큰수로 설정한다.)

이렇게 X,Y pair를 찾았다면, 직접 X의 약수갯수를 구해서 약수갯수 == Y인지 확인하면 된다.

Y가 2이상이므로 X는 10^9이하고 sqrt(N)복잡도로 약수를 구할 수 있다.

단, 정답은 최소임을 주의해야한다.