Розширений алгоритм Евкліда
Обмеження: 2 сек., 256 МіБ
Марічка і Зеник вернулися зі школи і одразу почали розв’язувати домашнє завдання.
На доманшнє завдання їм дали два натуральні числа \(a\) і \(b\). Їм необхідно знайти будь-який цілочисельний розв’язок рівняння: \(a \cdot x + b \cdot y = gcd(a, b)\), де \(gcd(a, b)\) — найбільший спільний дільник чисел \(a\) та \(b\).
Вхідні дані
У єдиному рядку задано два цілих числа \(a\) і \(b\).
Вихідні дані
У єдиному рядку виведіть цілі числа \(x\) та \(y\) — будь-який розв’язок рівняння.
Обмеження
\(1 \le a, b \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 2 | 1 -1 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 2 | 0 1 |
Джерело: Algotester Online Course S02E04
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|