Thuật toán Euclid mở rộng

Buổi 05 — Hàm & Đệ quy Number Theory
Points
32
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề 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$.

Draft saved