2782. Треугольник

Отдыхая на даче у Петиной бабушки, Петя и Вася решили построить секретный штаб для своей шпионской организации. Для размещения всей шпионской техники им необходимо помещение площадью ровно s квадратных метров. Стены штаба приходится строить из подручного материала, найденного у бабушки в сарае. Этим материалом оказались деревянные доски, каждая из которых имела длину ровно один метр. Выбирая форму штаба, Вася вспомнил последний урок геометрии, на котором они проходили прямоугольные треугольники, и предложил построить штаб в форме этой фигуры. Тем более, тогда они легко смогут посчитать его площадь и убедиться, что она равна требуемой.

Но тут оказалось, что пилы нет и поэтому доски никак не распилить. Васе с Петей придется строить штаб в форме прямоугольного треугольника, все стороны которого выражаются целым числом метров. Им стало интересно, сколько таких треугольников существует. При этом треугольники, имеющие одинаковые длины сторон, но отличающиеся их порядком, считаются одинаковыми.

Вход. Содержит единственное целое число s (1 ≤ s ≤ 10000) – требуемую площадь штаба.

Выход. Выведите одно целое число – количество возможных планов постройки штаба, площадь которого s квадратных метров.

Пример входа	Пример выхода
6	1

РЕШЕНИЕ

геометрия

Анализ алгоритма

Площадь прямоугольного треугольника со сторонами x и y равна s = (x * y) / 2. Найдем все возможные разложения числа 2s на множители x и y. Для каждой такой пары возможных катетов проверим, чтобы соответствующая ему гипотенуза имела целочисленную длину.

Пример

Площадь 6 имеет единственный прямоугольный треугольник с целочисленными длинами катетов 3 и 4.

Реализация алгоритма

Читаем входную площадь s штаба. Умножаем ее на 2.

scanf("%d", &s); s *= 2;

Перебираем возможные длины катетов треугольника x и y (x ≤ y).

for (x = 1; x <= sqrt(s); x++)

if (s % x == 0)

{

y = s / x;

Вычисляем длину гипотенузы zz и проверяем ее на целочисленность.

z = x * x + y * y;

zz = (int)(sqrt(z));

Если гипотенуза zz целочисленна, то имеем еще один треугольник с целочисленными сторонами. Увеличиваем res на 1.

if (zz * zz == z) res++;

}

Выводим ответ.

printf("%d\n", res);