19899번 - Полные квадраты 서브태스크다국어

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

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

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

В единственной строке содержится целое число k — начальное число в последовательности (−10¹² ⩽ k ⩽ 10¹²).

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

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

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

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

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