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

@TomikArtemik · Регистрация: 09.03.2020

Студворк — интернет-сервис помощи студентам

Даны натуральные числа a, b, c. Если уравнение ax+by=c имеет решения в целых числах, то выберите то решение, в котором число x имеет наименьшее неотрицательное значение, и выведите это решение (два числа x и y через один пробел). Если решения не существует, то выведите −1.

Входные данные

Входные данные — натуральные числа a, b и c. Числа заданы на одной строке через пробел и не превышают 109.

Выходные данные

Выведите ответ на задачу.

Примеры
Ввод
1 2 3
2 2 2
Вывод
1 1
0 1

Вот мой код, перепробовал много способов, но либо неправильный ответ, либо TLE

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
gcd = lambda m,n: m if not n else gcd(n,m%n)
 
a, b, c = map(int, input().split())
nod = gcd(a, b)
 
if c % nod != 0:
    print(-1)
else:
    for x in range(c):
        for y in range(c - a*x):
            if a*x + b*y == c:
                print(x, y, sep=' ')
                break

Помогите пожалуйста!

@Gdez · 14.09.2021, 00:03

TomikArtemik,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def gcd_extended(num1, num2):
    if num1 == 0:
        return (num2, 0, 1)
    else:
        div, x, y = gcd_extended(num2 % num1, num1)
    return (div, y - (num2 // num1) * x, x)
 
a, b, c = map(int, input().split())
d, x, y = gcd_extended(a,b)
 
if c % d == 0:
    k = c // d
    
    xi = x*k - (x*k) // b * b 
    if xi <= 0:
        xi += abs(b)
    yi = (c - xi*a) // b 
    
    print(xi, yi)
else:
    print(-1)

@TomikArtemik · 14.09.2021, 00:50 **[ТС]**

нет, программа выдаёт неправильный ответ

@Gdez · 14.09.2021, 06:34

TomikArtemik, Да - "х" неотрицательное, т.е. может и 0

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
 
 
a, b, c = map(int, input().split())
d, x, y = gcd_ext(a, b)
 
if c % d == 0:
    k = c//d
    t = k*x // (b//d)
    x = k*x - (b//d) * t
 
    if x < 0 :
        x = k*x + b//d
    y = (c - a*x) // b
    print(x, y)
else:
    print(-1)

enx · 14.09.2021, 19:41

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

А чтобы снизить риск TLE, пошустрее будет:

Python
1
from math import gcd

@TomikArtemik · 14.09.2021, 19:49 **[ТС]**

Спасибо огромное Gdez и enx!

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

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

Решение

Решение

@TomikArtemik 0 / 0 / 0 Регистрация: 09.03.2020 Сообщений: 6
	14.09.2021, 00:50 [ТС]
	нет, программа выдаёт неправильный ответ 0

@TomikArtemik 0 / 0 / 0 Регистрация: 09.03.2020 Сообщений: 6
	14.09.2021, 19:49 [ТС]
	Спасибо огромное Gdez и enx! 0