올림 없는 제곱근
시간 제한1초메모리 제한512 MB
정수 n이 주어질 때, 자릿수별 합에서 올림을 버리는 곱셈으로 제곱하면 n이 되는 가장 작은 양의 정수 a를 구하거나, 그러한 수가 없으면 -1을 출력한다.
문제
올림 없는 덧셈은 일반 덧셈과 같지만, 10진법에서 발생하는 올림을 모두 무시한다. 따라서 37 + 48은 85가 아니라 75이다.
올림 없는 곱셈은 일반적인 필산 곱셈 알고리즘을 각 자리마다 적용하되, 중간 합을 올림 없는 덧셈으로 계산한다. 예를 들어:
9 ∙ 1234 = 9000 + (900 + 900) + (90 + 90 + 90) + (9 + 9 + 9 + 9) = 9000 + 800 + 70 + 6 = 9876
90 ∙ 1234 = 98760
99 ∙ 1234 = 98760 + 9876 = 97536
형식적으로, c의 k번째 자릿수를 c_k라 하자. c = a · b이면
[c_k = \left[ \sum_{i+j=k}{a_i \cdot b_j} \right] \mod 10]
정수 n이 주어졌을 때, 올림 없는 곱셈에서 a ∙ a = n을 만족하는 가장 작은 양의 정수 a를 구하시오.
입력
입력은 정수 n 하나로 이루어진 한 줄이다. (1 ≤ n ≤ 10^25)
출력
입력된 수의 올림 없는 제곱근이 되는 가장 작은 양의 정수를 출력하거나, 그러한 수가 존재하지 않으면 −1을 출력한다.