완전제곱수
면접 대비시간 제한2초메모리 제한512 MB
정수 k에서 시작해 연속한 홀수를 더해 만든 수열 k, k+1, k+4, k+9, ...에서 제곱수가 나타나는 가장 작은 음이 아닌 정수를 구하고, 없으면 none을 출력한다.
문제
규칙성을 찾기 위해 특정 규칙에 따라 긴 수열을 생성하는 것이 유용할 때가 있다. 예를 들어 수열 0, 0+1, 0+1+3, 0+1+3+5, ..., 0+1+3+...+(2n-1), ...은 처음 몇 개의 홀수를 더한 합으로 이루어져 있으며, 정수의 제곱 0, 1, 4, 9, ..., n^2, ...으로 구성된다.
이 수열을 다음과 같이 일반화하자. 시작값으로 0 대신 수 k를 사용한다. 그러면 수열 k, k+1, k+1+3, k+1+3+5, ..., k+1+3+...+(2n-1), ...을 얻는다. k=0인 경우와 달리 이 수열에는 완전제곱수만 나타나지 않을 수 있다. 이 수열에 제곱이 나타나는 최소한의 음이 아닌 정수를 구해야 한다.
주어진 정수 k에 대해, 위 수열에 제곱이 나타나는 최소한의 음이 아닌 정수를 구하거나, 완전제곱수가 전혀 나타나지 않음을 판별하는 프로그램을 작성하시오.
입력
한 줄에 정수 k가 주어진다. k는 수열의 시작값이다. (-10^12 ≤ k ≤ 10^12)
이렇게 큰 수를 읽고 저장하려면 64비트 자료형을 사용해야 한다.
출력
위 수열에 제곱이 나타나는 최소한의 음이 아닌 정수를 출력한다. 수열에 정수의 제곱이 나타나지 않으면 «none»을 출력한다.
힌트
첫 번째 예에서 수열의 모든 수는 완전제곱수이다. 그중 최솟값은 0이고, 0^2 = 0이다.
두 번째 예에서 수열은 -5, -4, -1, 4, 11, 20, ...으로 시작한다. 수열에 제곱이 나타나는 최소한의 음이 아닌 정수는 2이고, 2^2 = 4이다.
세 번째 예에서 수열은 2, 3, 6, 11, 18, ...로 시작한다. 이 수열에는 정수의 제곱이 없다.