Nhật ký lời gọi Euclid

Bối cảnh và bài toán

Một bộ chẩn đoán chạy thuật toán Euclid theo dạng đệ quy gcd(a,b) -> gcd(b,a mod b) và muốn ghi nhận độ sâu xử lý. Mỗi lần hàm được gọi, kể cả lời gọi cuối cùng khi b=0, bộ đếm tăng thêm một.

Yêu cầu

Tính gcd(a,b) và tổng số lần hàm đệ quy được gọi theo đúng quy tắc trên.

Input

• Một dòng chứa hai số nguyên không âm a b, không đồng thời bằng 0.

Output

In gcd(a,b) và số lời gọi, cách nhau bởi một dấu cách.

Ràng buộc

• 0 <= a, b <= 10^18
• a + b > 0

Chấm điểm

Ví dụ 1

Input

48 18

Output

6 4

Giải thích. Các lời gọi là (48,18) -> (18,12) -> (12,6) -> (6,0).

Ví dụ 2

Input

10 0

Output

10 1

Giải thích. Lời gọi đầu tiên đã chạm base case.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.