Mã bài:
ts10tg_23_5
Điểm:
1,2 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
SHAPE.INP
Dữ liệu ra:
SHAPE.OUT
Tác giả:
Dạng bài
Bé Bo có một mảnh giấy hình chữ nhật gồm $m \times n$ ô vuông bằng nhau, với $m$ là chiều dài và $n$ là chiều rộng mảnh giấy. Bo tìm cách cắt từ mảnh giấy này để mỗi lần cắt được hình vuông có diện tích lớn nhất. Thao tác này được thực hiện nhiều lần như thế đối với phần giấy còn thừa lại cho đến khi hết giấy thừa.
Em hãy đếm số hình vuông mà Bo có thể cắt được.
Dữ liệu vào
Đọc từ file SHAPE.INP
gồm một dòng chứa hai số nguyên dương lần lượt là $m$ và $n$, giữa $m$ và $n$ được cách nhau bởi một dấu cách.
Kết quả ra
Ghi ra file SHAPE.OUT
một số nguyên dương là số hình vuông Bo cắt được.
Giới hạn
$1 \leq m, n \leq 10^9, m \geq n$.
Ví dụ 1
Dữ liệu
8 3
Kết quả
5
Giải thích
Ví dụ 2
Dữ liệu
21 4
Kết quả
9
Bình luận