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 đều áp dụng cùng thuật toán Euclid cho 48 và 18. Phiên bản recursion đi qua các cặp (48,18) → (18,12) → (12,6) → (6,0) rồi trả 6. Phiên bản loop cập nhật hai biến theo đúng chuỗi trạng thái đó cho đến khi số thứ hai bằng 0. Vì hai cách có cùng contract nên output là 6 6.

Ví dụ 2

Input

18 48

Output

6 6

Giải thích

Với a=7, b=13, thuật toán Euclid cho 13%7=6, 7%6=1, 6%1=0, nên GCD bằng 1. Cả recursion và iteration đều phải kết thúc ở cùng giá trị 1. Hai số 1 1 trong output cho thấy hai cách cài đặt tương đương về 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