| Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0 + 1, 0 + 1 + 3, 0 + 1 + 3 + 5, …, 0 + 1 + 3 + … + (2 n−1), …, составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, …, n2,….
Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, …, k + 1 + 3 + … + (2 n−1), …. В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.
Требуется написать программу, которая по заданному целому числу k определяет, квадрат какого минимального неотрицательного целого числа встречается в описанной последовательности, либо выясняет, что в ней вообще не встречается полных квадратов.
В единственной строке содержится целое число k — начальное число в последовательности. Обратите внимание, что для считывания и хранения такого большого числа необходимо использовать 64-битный тип данных.
Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной последовательности. Если в последовательности не встречается квадратов целых чисел, выведите none.
−1012 ≤ k ≤ 1012
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 7 | 1 ≤ k ≤ 1000 | полная | |
| 2 | 10 | 1 ≤ k ≤ 105 | 1 | первая ошибка |
| 3 | 27 | 1 ≤ k ≤ 1012 | 1, 2 | первая ошибка |
| 4 | 7 | −1000 ≤ k ≤ 1000 | 1 | полная |
| 5 | 10 | −105 ≤ k ≤ 105 | 1, 2, 4 | первая ошибка |
| 6 | 39 | −1012 ≤ k ≤ 1012 | 1, 2, 3, 4, 5 | первая ошибка |
В первом примере каждое число последовательности является полным квадратом. Минимальный из них — 0, 02 = 0.
Во втором примере последовательность начинается так: −5, −4, −1, 4, 11, 20,…. Минимальное неотрицательное целое число, квадрат которого встречается в последовательности — 2, 22 = 4.
В третьем примере последовательность начинается так: 2, 3, 6, 11, 18, …. В ней нет квадратов целых чисел.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|