Найти все возможные значения длины гипотенузы в прямоугольном треугольнике с целыми сторонами, если один из катетов имеет длину p, где p - простое число.

Напоминаем, что простым называется целое положительное число, имеющее ровно два делителя - единицу и самого себя.

Формат ввода

Входные данные содержат одно целое число p (2 ≤ p ≤ 109+9, p - простое).

Формат вывода

Если пифагоровых треугольников с катетом длины p нет, выведите - 1. Иначе выведите возможные длины гипотенуз треугольников, перечисленные в порядке возрастания (то есть от меньшей к большей).

Пример

Ввод 3

Вывод 5

Примечания

Пояснение к примеру: cуществует только один целочисленный прямоугольный треугольник с катетом равным 3 - классический пифагоров треугольник c длиной гипотенузы, равной 5.

Question

Информатика

Афмзе

14 января, 23:21

Найти все возможные значения длины гипотенузы в прямоугольном треугольнике с целыми сторонами, если один из катетов имеет длину p, где p - простое число.

Напоминаем, что простым называется целое положительное число, имеющее ровно два делителя - единицу и самого себя.

Формат ввода

Входные данные содержат одно целое число p (2 ≤ p ≤ 109+9, p - простое).

Формат вывода

Если пифагоровых треугольников с катетом длины p нет, выведите - 1. Иначе выведите возможные длины гипотенуз треугольников, перечисленные в порядке возрастания (то есть от меньшей к большей).

Пример

Ввод 3

Вывод 5

Примечания

Пояснение к примеру: cуществует только один целочисленный прямоугольный треугольник с катетом равным 3 - классический пифагоров треугольник c длиной гипотенузы, равной 5.

+4

Ответы (2)

Знаете ответ на вопрос?

Аполиния · Answer 1

Решение существует всегда, причем единственное, если p - простое.

Программа на Питоне.

p=int (input ())

n = (p*p-1) / / 2+1

print (n)

Аметабх · Answer 2

import math

p = int (input ())

b = False

for i in range (1, p * * 2) :

gip = (p * * 2) + (i * * 2)

if math. sqrt (gip) % 1 = = 0:

b = True

if int (math. sqrt (gip)) ! = p:

print (int (math. sqrt (gip)))

if b = = False:

print (-1)

# что-то типо этого, но не проходит по времени. Надо смотреть диапазон. Может если кто дорешает, ответьте. а так всё норм работает)