GCD đệ quy

Bối cảnh

Bạn đã biết Euclid dạng vòng lặp. Hãy viết lại đúng quan hệ gcd(a,b)=gcd(b,a%b) bằng recursion.

Input có thể chứa số âm; GCD được lấy không âm.

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

48,18 -> 18,12 -> 12,6 -> 6,0, nên GCD bằng 6.

Ví dụ 2

Input

18 48

Output

6

Giải thích

Thuật toán vẫn hoạt động khi số thứ hai lớn hơn số thứ nhất; kết quả cũng bằng 6.

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