Задача: Диафантово уравнение, python

Question

Диофантово уравнение

Даны натуральные числа 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)

Answer 1

Можно банально перебором, если x тоже не больше 10⁹ предполагается:

Выводите уравнение, чему равно y из вашей формулы при заданных a, b, c и x.
Перебираете x от 0 до 10⁹.
Если вычисленное y при таком x получается целое, то всё, конец перебора, выводим результат.
Если перебор закончился, а результата нет - выводим -1.

Код сами если что напишете, он элементарный.

Answer 2

import os

print("-" * 65 + "\nДиофантово уравнение:\n" + "-" * 65)

def extended_gcd(a, b):
 if a == 0: return b, 0, 1  # Базовый случай: если a равно 0, возвращаем b, 0 и 1
 gcd, x1, y1 = extended_gcd(b % a, a)  # Рекурсивный вызов с b % a и a
 x = y1 - (b // a) * x1
 y = x1
 return gcd, x, y  # Возвращаем НОД и коэффициенты x и y

def solve_diophantine(a, b, c):
 gcd, x, y = extended_gcd(a, b)  # Находим НОД и коэффициенты x и y
 if c % gcd != 0: return -1  # Если c не делится на НОД, решения не существует
 x *= c // gcd  # Масштабируем x на c // gcd
 y *= c // gcd  # Масштабируем y на c // gcd
 if x < 0:  # Если x отрицательное, находим наименьшее неотрицательное значение
  k = (-x + b // gcd - 1) // (b // gcd)
  x += k * (b // gcd)
  y -= k * (a // gcd)
 return x, y

# Пример значений из условия:
a, b, c = 1, 2, 3  # Пример 1
# a, b, c = 2, 2, 2  # Пример 2

# Решение уравнения:
result = solve_diophantine(a, b, c)

# Вывод результата:
if result == -1: print(-1)
else: print("x, y:", result[0], result[1])

print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")

БЛОГ НА HUSL

Задача: Диафантово уравнение, python

Диофантово уравнение

Ответы (2 шт):