시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 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».

서브태스크

번호 배점 조건
1 7

0 ⩽ k ⩽ 1000

2 10

0 ⩽ k ⩽ 105

3 27

0 ⩽ k ⩽ 1012

4 7

−1000 ⩽ k ⩽ 1000

5 10

−105 ⩽ k ⩽ 105

6 39

−1012 ⩽ k ⩽ 1012

예제 입력 1

0

예제 출력 1

0

예제 입력 2

-5

예제 출력 2

2

예제 입력 3

2

예제 출력 3

none

힌트

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

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

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.