Link Sub: http://www.spoj.com/PTIT/problems/P144SUMI/
Người Gửi: Dương Lee
- Problem:
Sau giờ học, Tí cùng các bạn rủ nhau đi ăn xúc xích. Mọi người cùng nhau góp tiền. Có tất cả M người nhưng số tiền mà Tí cùng các bạn có chỉ mua được N cái xúc xích. Để cho công bằng thì Tí sẽ chia đều N chiếc xúc xích cho tất cả mọi người. Với một con dao trong tay, các bạn hãy giúp Tí tính xem Tí cần cắt ít nhất bao nhiêu phát?
Input
Gồm 2 số nguyên n và m (n, m <= 100).
Output
In ra một số nguyên duy nhất là đáp án của bài toán.
Example:
In ra một số nguyên duy nhất là đáp án của bài toán.
Input
2 6
Output:
4
Input
3 4
Output:
3
Input
6 2
Output:
0
- Solution:
Giải thích test 1: Có 2 cái xúc xích và cần chia ra thành 6 phần, Tí sẽ cắt mỗi chiếc xúc xích ra thành 3 phần đều nhau, như vậy cần tổng cộng 4 lát cắt.Input
3 4
Output:
3
Input
6 2
Output:
0
Cách làm:
- Áp dụng tham lam như hình vẽ:
Trên hình là cách chia 3 xúc xích cho 4 người (Vạch đỏ là nơi cắt xúc xích) - Như vậy: + Lấy bội chung của số xúc xích và số người ta sẽ xác định được mỗi người sẽ cần tương ứng với bao nhiêu phần xúc xích. (Lấy bội chung thì lúc chia phần sẽ luôn nguyên). VD: 3 4 -> BC=12; -> một người cần 3 phần xúc xích. + Tham lam: Mỗi người ta sẽ lấy đủ phần xúc xích (thiếu thì lấy thêm không may lấy thừa thì sẽ cắt bớt). VD: người 1 cần 3 phần: + Lấy xúc xích 1: được 4 phần; (4 > 3: cắt bớt: cắt++; dư: 1 phần) -> người 1: đủ. + Lấy xúc xích 2: được 4 + 1 phần; (5 > 3: cắt bớt; cắt++; dư 2 phần) -> người 2: đủ. + lấy xúc xích 3: được 4 + 2 phần; (6 > 3: cắt bớt; cắt++; dư 3 phần) -> người 3: đủ. + Còn lại 3 phần cho người thứ 4;