Олимпиада по информатике срочно
Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы четырех точных квадратов. По данному числу
найдите такое представление: напечатайте
целых неотрицательных числа, квадраты которых дают в сумме данное число.
Формат входных данных
Программа получает на вход одно натуральное число
.
Формат результата
Программа должна вывести
целых неотрицательных числа, квадраты которых дают в сумме данное число.
Примеры
Входные данные
7
Результат работы
1 1 1 2
помогите пожалуста
n = int(input())
for a in range(int(n**0.5)+1):
ost = n-a*a
for b in range(int(ost**0.5)+1):
ost2=ost-b*b
for c in range(int(ost2**0.5)+1):
ost3=ost2-c*c
if ost3>=0 and int(ost3**0.5)**2==ost3:
d=int(ost3**0.5)
print(a,b,c,d)
exit()
С++:
#include <iostream>
#include <cmath>
int main() {
int target;
std::cin >> target;
for (int a = 0; a * a <= target; ++a)
for (int b = 0; b * b <= target - a * a; ++b)
for (int c = 0; c * c <= target - a * a - b * b; ++c) {
int d = std::sqrt(target - a * a - b * b - c * c);
if (d * d == target - a * a - b * b - c * c) {
std::cout << a << " " << b << " " << c << " " << d << std::endl;
return 0;
}
}
} Подозреваю, что данные не велики и такое решение должно подойти.