Здравствуйте, помогите пожалуйста решить задачу из курса Сириуса, язык Python
Диофантово уравнение
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение, и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите −1.
Входные данные
Входные данные — натуральные числа a, b и c. Числа заданы на одной строке через пробел и не превышают 109.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод
1 2 3
2 2 2
Вывод
1 1
0 1
По дате
По Рейтингу
1234567891011121314151617181920212223242526272829303132
import time
def gcd(a, b):
while a != b:
if a > b:
a, b = b, a
b = b - a
return a
a, b, c = int(input()), int(input()), int(input())
print("\nуточнение: a*x + b*y = c\n")
print(f"Ввод данных: a = {a}, b = {b}, c = {c}.\n")
the_time = time.clock()
d = gcd(a, b)
if c % d != 0:
print("Невыполнимый!")
if c % d == 0:
a //= d
b //= d
c //= d
for k in range(a+1):
if (c-b*k) % a == 0:
y = k
x = (c-(b*k)) // a
else:
print("\nНичего не происходит\n")
break
seconds = (time.clock() - the_time) / time.CLOCKS_PER_SEC
print(f"output data: x = {x}, y = {y}.\n")
print(f"runtime: {seconds} sec.\n") Больше по теме