Hai cách tính GCD

Bối cảnh

Bạn cần chứng minh hai mô hình recursion và iteration cho cùng một thuật toán Euclid.

Chương trình phải tính GCD bằng cả hai hàm và in hai kết quả để kiểm tra chúng trùng nhau.

Yêu cầu

1. Viết gcdRec(a,b) bằng recursion.
2. Viết gcdLoop(a,b) bằng while.
3. In recursive iterative.

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

Phải có cả hai hàm, một recursion và một iteration.

Online Judge chủ yếu chấm output. Giảng viên sẽ quan sát thêm cách tổ chức hàm khi review code để bảo đảm học viên luyện đúng kỹ năng của buổi.

Input

Hai số nguyên a b.

Output

Một dòng gồm hai kết quả.

Ràng buộc

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

Ví dụ 1

Input

48 18

Output

6 6

Giải thích

Cả hai phiên bản Euclid đều trả 6 nên output là 6 6.

Ví dụ 2

Input

18 48

Output

6 6

Giải thích

Đổi thứ tự input không làm thay đổi GCD; cả hai hàm vẫn trả cùng kết quả.

Thông tin học tập

• Module: M04
• Buổi: B14
• Loại bài: LAB
• Độ khó: Medium
• Concepts: recursion vs iteration, Euclidean algorithm, function design
• Giới hạn kiến thức: B01-B14
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100