← Назад к математике

Расширенный алгоритм Евклида

Нахождение коэффициентов x, y для уравнения ax + by = gcd(a, b)

🐍 Python
def gcdex(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = gcdex(b, a % b)
        return d, y, x - y * (a // b)

a, b, c = map(int, input().split())
d, x, y = gcdex(a, b)

if d != 0 and c % d == 0:
    x *= (c // d)
    y *= (c // d)
    x0 = x
    x %= (b // d)
    k = (x - x0) // (b // d)
    y -= k * a // d
    print(x, y)
else:
    print(-1)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

long long gcdex(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long d = gcdex(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

int main() {
    long long a, b, c;
    cin >> a >> b >> c;
    
    long long x, y;
    long long d = gcdex(a, b, x, y);
    
    if (c % d != 0) {
        cout << -1 << endl;
        return 0;
    }
    
    x *= (c / d);
    y *= (c / d);
    
    cout << x << " " << y << endl;
    return 0;
}

Как работает расширенный алгоритм Евклида?

Расширенный алгоритм Евклида находит не только НОД(a, b), но и коэффициенты x, y, удовлетворяющие уравнению:

a·x + b·y = gcd(a, b)

Основная идея

Из обычного алгоритма Евклида: НОД(a, b) = НОД(b, a mod b). На обратном ходу рекурсии находим x и y.

Решение уравнения a·x + b·y = c

Уравнение имеет решение, только если c делится на НОД(a, b).

Применения

Временная сложность: O(log min(a, b))

Формат ввода и вывода

Ввод: a, b, c — коэффициенты уравнения a·x + b·y = c

Вывод: x y — одно из решений, или -1, если решений нет

Пример:

2 3 1

2·(-1) + 3·1 = 1 → (-1, 1)

Вывод: -1 1

Попробовать онлайн

Результат появится здесь...