Chia xúc xích

Time limit: 1.0s , Memory limit: 250M , Points: 10 (partial)

Bi có $n$ ~n~ thanh xúc xích với chiều dài bằng nhau, hôm nay Bi tổ chức tiệc nhỏ cho $m$ ~m~ người bạn của mình và có một vấn đề cần giải quyết đó là làm sao cắt $n$ ~n~ thanh xúc xích trên để chia đều cho $m$ ~m~ người bạn, và để các thanh xúc xích đẹp khi chia đều thì cần cắt với ít lần cắt nhất có thể.

Xét ví dụ $n = 2, m = 8$ ~n = 2, m = 8~ mỗi xúc xích cắt $3$ ~3~ nhát ta có được $8$ ~8~ phần bằng nhau và chia đều cho $8$ ~8~ người, vậy mất $6$ ~6~ nhát cắt.

Hãy lập trình giúp Bi giải quyết vấn đề trên.

Input

Dòng duy nhất chứa hai số nguyên là $n, m$ ~n, m~ thỏa $1 \le n, m \le 100$ ~1 \le n, m \le 100~.

Output

In ra số lát cắt ít nhất có thể.

Samples

Sample Input 1

2 8

Sample Output 1

Sample Input 2

5 9

Sample Output 2

Sample Input 3

4 2

Sample Output 3

Comments

6
nhan0510 commented on Aug. 31, 2023, 9:04 a.m.
Ý Tưởng Thuật Toán

Khái Quát

Bài toán yêu cầu chia ( n ) thanh xúc xích có độ dài giống nhau cho ( m ) người sao cho số lần cắt là ít nhất. Để giải quyết vấn đề này, chúng ta sẽ tận dụng tính chất của Ước chung lớn nhất (GCD - Greatest Common Divisor).

Tại sao sử dụng GCD?

Quan sát bài toán, ta thấy rằng mục tiêu là chia ( n ) thanh xúc xích cho ( m ) người. Một cách để làm điều này là cắt mỗi thanh xúc xích thành các miếng nhỏ hơn sao cho tổng số miếng là bội số của ( m ). Điều này đảm bảo rằng mỗi người sẽ nhận được số lượng miếng xúc xích giống nhau.

Tại đây, GCD của ( n ) và ( m ) sẽ cho ta biết số lượng "nhóm" mà ( m ) có thể được phân chia. Điều này giúp ta tối ưu số lần cắt.

Phương Pháp Giải Quyết

Tính GCD của ( n ) và ( m ): Sử dụng thuật toán Euclidean để tính GCD.

[ \text{GCD}(n, m) ]

Số lát cắt ít nhất: Số lát cắt ít nhất cần để chia đều ( n ) thanh xúc xích cho ( m ) người sẽ là:

[ \text{Số lát cắt} = m - \text{GCD}(n, m) ]

Giả sử ( \text{GCD}(n, m) = g ), điều này có nghĩa là ( m ) người có thể được phân thành ( g ) nhóm, mỗi nhóm có ( \frac{m}{g} ) người. Do đó, mỗi nhóm sẽ nhận được ( n ) thanh xúc xích, và chúng ta chỉ cần cắt mỗi thanh xúc xích thành ( \frac{m}{g} ) miếng. Tổng số lát cắt cho ( n ) thanh xúc xích là ( n \times \left( \frac{m}{g} - 1 \right) = m - g ).

Chúng ta có thể thực hiện tất cả những bước này trong thời gian ( O(\log \min(n, m)) ) nhờ việc tính GCD, đáp ứng yêu cầu về hiệu suất của bài toán.
Link