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

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0 + 1, 0 + 1 + 3, 0 + 1 + 3 + 5, , 0 + 1 + 3 + … + (2 n1), , составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, …, n2,….

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

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

Формат входных данных

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

Формат выходных данных

Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной последовательности. Если в последовательности не встречается квадратов целых чисел, выведите none.

Ограничения

1012 ≤ k ≤ 1012

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
171 ≤ k ≤ 1000полная
2101 ≤ k ≤ 1051первая ошибка
3271 ≤ k ≤ 10121, 2первая ошибка
471000 ≤ k ≤ 10001полная
510105 ≤ k ≤ 1051, 2, 4первая ошибка
6391012 ≤ k ≤ 10121, 2, 3, 4, 5первая ошибка

Пояснения к примерам

В первом примере каждое число последовательности является полным квадратом. Минимальный из них — 0, 02 = 0.

Во втором примере последовательность начинается так: 5, −4, −1, 4, 11, 20,…. Минимальное неотрицательное целое число, квадрат которого встречается в последовательности — 2, 22 = 4.

В третьем примере последовательность начинается так: 2, 3, 6, 11, 18, …. В ней нет квадратов целых чисел.

Примеры тестов

Стандартный вход Стандартный выход
1
0
0
2
-5
2
3
2
none

0.054s 0.008s 15