제곱으로 나누어지지 않는 수
시간 제한2초메모리 제한128 MB
K가 최대 10억일 때, 계수 함수와 이분 탐색을 이용해 K번째 제곱 인수가 없는 양의 정수를 구하는 문제입니다.
문제
양의 정수 N이 1보다 큰 어떤 제곱수로도 나누어떨어지지 않으면, N을 제곱으로 나누어지지 않는 수라고 한다. 예를 들어 4, 9, 16, 25는 제곱수이고, 1, 2, 3, 5, 6, 7, 10, 11, 13, ...은 1보다 큰 제곱수로 나누어떨어지지 않는다.
K가 주어질 때, 오름차순으로 나열한 제곱으로 나누어지지 않는 수 중 K번째 수를 구하시오.
입력
첫째 줄에 정수 K가 주어진다.
출력
첫째 줄에 K번째 제곱으로 나누어지지 않는 수를 출력한다.
제한
- 1 ≤ K ≤ 1,000,000,000