Problem ID:
ts10tg_23_5
Points:
1.2 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
SHAPE.INP
Output:
SHAPE.OUT
Author:
Problem type
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
Comments