Диофантово уравнение
Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение, и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите −1.
Входные данные
Входные данные — натуральные числа a, b и c. Числа заданы на одной строке через пробел и не превышают 10⁹.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод: 1 2 3
Вывод: 1 1
Ввод: 2 2 2
Вывод: 0 1
Написал данный код, однако он прошел 63/65 тестов, можете подсказать ошибку?
import math
def gcd_ext(a, b):
if b == 0:
return a, 1, 0
d, x, y = gcd_ext(b, a % b)
x, y = y, x - (a // b) * y
return d, x, y
def solve_eq(a, b, c):
d, x0, y0 = gcd_ext(a, b)
if c % d != 0:
return False, None
t = math.ceil(-c / b * x0)
x = c / d * x0 + b / d * t
y = c / d * y0 - a / d * t
return True, (int(x), int(y))
a, b, c = map(int, input().split())
has_result, ans = solve_eq(a, b, c)
if has_result:
print(ans[0], ans[1])
else:
print(-1)