GCD của hai số

Bối cảnh

Hai cảm biến đo chu kỳ lặp lại theo hai khoảng thời gian khác nhau. Để phân tích nhịp chung, hệ thống cần tìm ước chung lớn nhất của hai giá trị.

Thay vì duyệt toàn bộ các ước, bạn sẽ sử dụng thuật toán Euclid — một thuật toán cổ điển nhưng rất hiệu quả.

Yêu cầu

1. Đọc hai số nguyên a, b.
2. Tính gcd(|a|, |b|) bằng thuật toán Euclid.
3. In GCD.

Yêu cầu tổ chức code

Tạo hàm gcdEuclid(a,b) và gọi từ main.

Lưu ý: Online Judge chủ yếu kiểm tra tính đúng của output. Yêu cầu tổ chức code được dùng để rèn đúng kỹ năng của buổi học và sẽ được giảng viên quan sát khi chữa bài.

Input

Hai số nguyên a b.

Output

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

Ràng buộc

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

Ví dụ 1

Input

48 18

Output

6

Giải thích

Euclid: 48 % 18 = 12, rồi 18 % 12 = 6, cuối cùng 12 % 6 = 0. GCD là 6.

Ví dụ 2

Input

-48 18

Output

6

Giải thích

Dấu âm không ảnh hưởng GCD; ta làm việc với trị tuyệt đối nên gcd(-48,18) = 6.

Thông tin học tập

• Module: M02
• Buổi: B07
• Loại bài: LAB
• Độ khó: Easy
• Concepts: functions, Euclidean algorithm, modulo operator
• Giới hạn kiến thức: B01-B07
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100