e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Месть Пифагора

Месть Пифагора

Знаменитая теорема Пифагора утверждает, что прямоугольный треугольник с длинами сторон A и B и длиной гипотенузы C удовлетворяет формуле A2 + B2 = C2. Также известно, что существуют прямоугольные треугольники с целочисленными длинами всех трех сторон. Например:

prb10100.gif

Еще примеры с A = 12:

prb10100_1.gif

По заданному целому значению A найдите количество таких различных целых B > A, для которых существует целочисленная гипотенуза C.

Входные данные

Каждая строка содержит одно целое число A (2A < 1048576 = 220). Последняя строка содержит 0 и не обрабатывается.

Выходные данные

Для каждого значения A выведите количество таких целых B > A, что существует прямоугольный треугольник со сторонами A, B и целочисленной гипотенузой.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
12
2
1048574
1048575
0
Вихідні дані #1
1
2
0
1
175
Джерело 2012 ACM North America, Mid-Central, Задача A