GCD đệ quy

Bối cảnh

Hai bộ đếm của một hệ thống cần được đồng bộ theo chu kỳ chung. Bài toán quy về tìm ước chung lớn nhất của hai số nguyên bằng thuật toán Euclid đã học ở Module 02, nhưng lần này phải cài lại bằng recursion. Đây là một homework Easy nhằm củng cố cách chuyển một thuật toán lặp quen thuộc thành quan hệ đệ quy: thay vì cập nhật (a,b) trong vòng lặp, mỗi tầng gọi tiếp với (b, a%b). Học viên cần theo dõi invariant của Euclid — GCD không thay đổi sau phép biến đổi — và xác định base case khi số thứ hai bằng 0. Ý nghĩa toán học không đổi; trọng tâm là cấu trúc lời gọi và dòng chảy của giá trị trả về.

Yêu cầu

1. Chuẩn hóa dấu nếu cần.
2. Nếu b=0, trả |a|.
3. Nếu chưa, gọi gcd(b,a%b).
4. In kết quả.

Input

Hai số nguyên a b.

Output

Một số nguyên không âm.

Ràng buộc

|a|,|b| ≤ 10^12, không đồng thời bằng 0.

Ví dụ 1

Input

48 18

Output

6

Giải thích

Với 48 và 18, recursion đi qua gcd(48,18)→gcd(18,12)→gcd(12,6)→gcd(6,0). Khi b bằng 0, base case trả 6. Các tầng phía trên không cần tính thêm mà chỉ chuyển tiếp giá trị này về main, nên output cuối cùng là 6.

Ví dụ 2

Input

18 48

Output

6

Giải thích

Với 7 và 13, do 7 nhỏ hơn 13 nên bước đầu tạo gcd(13,7). Sau đó 13%7=6, 7%6=1 và 6%1=0, nên chuỗi lời gọi kết thúc tại gcd(1,0). Base case trả 1 và giá trị này được truyền ngược qua toàn bộ call stack. Điều đó cho biết 7 và 13 chỉ có ước chung dương là 1, nên output là 1.

Thông tin học tập

• Module: M04
• Buổi: B13
• Loại bài: HOMEWORK
• Độ khó: Easy
• Concepts: recursion, Euclidean algorithm, modulo, base case
• Giới hạn kiến thức: B01-B13
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100