Олимпиадный тренинг

Задача . Полные квадраты


С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0+ 1, 0+ 1+ 3, 0+ 1+ 3+ 5,
. . . , 0 + 1 + 3 + . . . + (2n − 1), . . ., составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, . . . , n2, . . ..
Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, . . . ,k+ 1+ 3+. . .+ (2n−1), . . ..  В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

Требуется написать программу, которая по заданному целому числу k определяет, квадрат какого минимального неотрицательного целого числа встречается в описанной последовательности,
либо выясняет, что в ней вообще не встречается полных квадратов.

Формат входных данных
В единственной строке содержится целое число k — начальное число в последовательности
(−1012 <= k <= 1012).
Обратите внимание, что для считывания и хранения такого большого числа необходимо использовать 64-битный тип данных.

Формат выходных данных
Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной
последовательности. Если в последовательности не встречается квадратов целых чисел, выведите
«none».
 
Ввод Вывод
0 0
-5 2
2 none
 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя