Rozszerzony algorytm Euklidesa

Rozszerzony algorytm Euklidesa jest modyfikacją klasycznego algorytmu Euklidesa, który służy do obliczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych. Problemem, który rozwiązuje rozszerzony algorytm Euklidesa, jest znalezienie rozwiązań równania Diofantycznego postaci \(ax + by = NWD(a,b)\), gdzie \(a\) i \(b\) są liczbami całkowitymi, a \(x\) i \(y\) są niewiadomymi. Jest to przydatne w wielu dziedzinach, takich jak kryptografia, teoria liczb, matematyka dyskretna czy programowanie liniowe.

Specification

Input

• \(a, b\) — liczby naturalne, większe od zera

Output

• \(x, y\) - liczby całkowite, takie że \(ax + by = NWD(a,b)\)
• \(NWD(a, b)\) — największy wspólny dzielnik liczb \(a\) i \(b\)

Example

Input

a := 6
b := 21

Output

x := -3
y := 1
NWD(a, b) := 3

Info

Wyjaśnienie

\(6 * (-3) + 21 * 1 = 3\)

Implementation

C++

Python