Thuật toán Euclid mở rộng
Points
32
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Đề bài
Cho hai số nguyên dương $a$ và $b$. Hãy sử dụng thuật toán Euclid mở rộng đệ quy để tìm $g = \gcd(a, b)$ và cặp số nguyên $(x, y)$ thỏa mãn phương trình $ax + by = g$ (với trường hợp cơ sở chuẩn $b = 0 \Rightarrow x = 1, y = 0$).
Dữ liệu vào
Một dòng chứa hai số nguyên dương $a$ và $b$.
Dữ liệu ra
Một dòng chứa ba số nguyên $g, x, y$ cách nhau bởi dấu cách.
Ví dụ
| Input | Output |
|---|---|
| 30 20 | 10 1 -1 |
| 17 13 | 1 -3 4 |
Giới hạn
$1 \le a, b \le 10^9$.
Community Discussion