Easy
시간 제한5초메모리 제한512 MB
n이 10^18 이하로 주어질 때, 뫼비우스 함수와 이분 탐색으로 n번째 제곱ㄴㄴ수를 구한다.
문제
어떤 정수가 1이 아닌 제곱수로 나누어지지 않으면, 이 수를 제곱ㄴㄴ수라고 부릅니다. 제곱ㄴㄴ수의 예시로 6, 17, 30 등이 있습니다. 키파의 생일과 관련이 있는 수 4, 12, 98, 1204, 1998, 19981204는 모두 제곱ㄴㄴ수가 아니네요.
나와 관련있는 수가 제곱수로 이렇게 허무하게 나누어지다니! 자존심이 상한 키파는 제곱 ㄴㄴ의 제한을 제곱하기로 했습니다.
n이 주어졌을 때, n번째 제곱ㄴㄴ수를 구하는 프로그램을 작성하세요.
입력
첫째 줄에 1018보다 작거나 같은 양의 정수 n이 주어집니다.
출력
첫째 줄에 n번째 제곱ㄴㄴ수를 출력합니다.