Ước/Bội chungSố học
Mô tả
Lễ hội làng Việt Nam đang diễn ra náo nhiệt. Ban tổ chức chuẩn bị hai đống kẹo truyền thống: một đống có a viên kẹo mứt dừa và một đống có b viên kẹo bánh đậu. Để phần thưởng của các đội tham gia trò chơi dân gian được công bằng, ban tổ chức muốn chia toàn bộ số kẹo này thành các gói nhỏ sao cho:
- Mỗi gói đều có chung một số lượng kẹo mứt dừa.
- Mỗi gói đều có chung một số lượng kẹo bánh đậu.
- Mọi viên kẹo đều được dùng hết, không thừa viên nào.
- Số lượng kẹo mứt dừa (và bánh đậu) trong mỗi gói phải lớn nhất có thể.
Nhiệm vụ của bạn là tìm số lượng kẹo mứt dừa trong mỗi gói (cũng chính là số lượng kẹo bánh đậu trong mỗi gói).
Đầu vào
- Một dòng chứa hai số nguyên dương
avàb(1 ≤ a, b ≤ 10^9), cách nhau bởi một dấu cách.
Đầu ra
- In ra một số nguyên duy nhất là số lượng kẹo lớn nhất trong mỗi gói.
Ràng buộc
- 1 ≤ a, b ≤ 10^9
- Time limit: 2 giây.
Ví dụ
Ví dụ 1:
- Đầu vào:
24 36 - Đầu ra:
12 - Giải thích: Có thể chia thành 12 gói, mỗi gói 2 viên mứt dừa và 3 viên bánh đậu. Hoặc chia thành 6 gói, mỗi gói 4 viên mứt dừa và 6 viên bánh đậu. Cách chia khiến mỗi gói chứa nhiều kẹo nhất là 12 viên/gói.
Ví dụ 2:
- Đầu vào:
17 5 - Đầu ra:
1 - Giải thích: Vì 17 là số nguyên tố và 17 không chia hết cho 5, nên hai đống kẹo không có ước chung nào lớn hơn 1. Mỗi gói chỉ chứa 1 viên kẹo.