Một kiến trúc sư có một tấm gỗ dài A cm và rộng B cm. Bác muốn cắt toàn bộ tấm gỗ thành các tấm hình vuông bằng nhau có kích thước lớn nhất có thể mà không để lại gỗ thừa.

Yêu cầu: Tìm kích thước cạnh hình vuông lớn nhất đó (bản chất là tìm Ước chung lớn nhất của A và B).

Một dòng chứa hai số nguyên dương A và B (1 ≤ A, B ≤ 10⁹).

Một số nguyên duy nhất là ước chung lớn nhất của A và B.

+ Giới hạn số khá lớn nên không thể duyệt từ 1 đến min(A, B). Hãy dùng thuật toán Euclid tối ưu.

Bài tập yêu cầu nhập dữ liệu từ thiết bị nhập chuẩn (bàn phím/stdin) và xuất kết quả ra thiết bị xuất chuẩn (màn hình/stdout). Tuyệt đối không đọc/ghi từ tệp tin (file).