Hiểu bài toán

Bạn có ~n~ cái bánh ban đầu là 1 phần nguyên vẹn. Bạn muốn chia chúng cho ~m~ người sao cho mỗi người nhận được lượng bánh như nhau (tổng lượng bánh là ~n~, mỗi người nhận ~n/m~). Bạn chỉ có thể dùng dao cắt, mỗi lần cắt chia một phần bánh существ tại thành 2 phần có tỉ lệ tự do (không nhất thiết bằng nhau). Mục tiêu là tìm số lần cắt tối thiểu để có ít nhất ~m~ phần bánh có thể phân phối cho ~m~ người (mỗi người 1 phần). Lưu ý rằng có thể cắt một phần bánh thành nhiều phần nhỏ hơn, nhưng chỉ cần đủ ~m~ phần để chia.

Các cách tiếp cận

Cách Công thức dựa trên ước chung (GCD)

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n, m;
    cin >> n >> m;
    long long g = std::gcd(n, m);
    cout << (m - g) << "\n";
    return 0;
}

• Time Complexity: O(log min(n, m))
• Space Complexity: O(1)

Gọi ~g = gcd(n, m)~. Ta có thể coi bài toán chia ~n~ bánh cho ~m~ người tương đương với việc chia ~n/g~ bánh cho ~m/g~ người (vì ~n/g~ và ~m/g~ nguyên tố cùng nhau). Với 1 phần ban đầu, để có được ~k~ phần bằng nhau (~k~ là số người tương ứng trong bài toán quy nạp), ta cần ~k-1~ lần cắt. Tuy nhiên, ta không cần chia nhỏ tất cả các phần bánh hiện có. Ban đầu có ~g~ nhóm bánh (mỗi nhóm ~n/g~ cái), mỗi nhóm cần được chia cho ~m/g~ người. Do đó, tổng số lần cắt tối thiểu là ~g * ((m/g) - 1) = m - g~.

Cách Công thức nhân tử số

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n, m;
    cin >> n >> m;
    long long g = __gcd(n, m);
    long long k = m / g;
    cout << (k - 1) * g << "\n";
    return 0;
}

• Time Complexity: O(log min(n, m))
• Space Complexity: O(1)

Đây là cách diễn giải khác của lời giải GCD. Để chia ~n~ bánh cho ~m~ người, ta cần chia đều cho ~g~ nhóm bánh ban đầu. Mỗi nhóm bánh ban đầu cần được chia cho ~m/g~ người. Việc chia 1 phần (hoặc 1 nhóm nguyên liệu) cho ~k~ phần bằng nhau cần tối thiểu ~k-1~ lần cắt. Vậy tổng số lần cắt là ~g * ((m/g) - 1)~.

Cách Quy nạp logic

// Logic suy nghĩ
// Nếu n chia hết cho m: Coi n/m nhóm, mỗi nhóm 1 bánh. Mỗi nhóm cần chia cho 1 người -> 0 cắt.
// Nếu n không chia hết cho m: Gọi g = gcd(n, m).
// Chia bài toán thành g bài toán nhỏ: chia n/g bánh cho m/g người.
// Cần tối thiểu (m/g - 1) lần cắt cho 1 đơn vị.
// Tong: g * (m/g - 1) = m - g.

• Time Complexity: O(log min(n, m))
• Space Complexity: O(1)

Xét ví dụ n=3, m=5. ~gcd(3, 5) = 1~. ~m/g = 5~. Cần ~5-1 = 4~ lần cắt. Xét ví dụ n=6, m=8. ~gcd(6, 8) = 2~. ~m/g = 4~. Cần ~2 * (4 - 1) = 6~ lần cắt. Logic cơ bản là: Bạn có thể coi bài toán là chia đều ~n/g~ đơn vị nguyên liệu cho ~m/g~ người. Với mỗi đơn vị nguyên liệu đó, bạn cần ~m/g - 1~ lần cắt để tạo ra ~m/g~ phần bằng nhau.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán chia ~n/g~ bánh cho ~m/g~ người, trong đó ~g = gcd(n, m)~.
• Để chia 1 phần bánh thành ~k~ phần bằng nhau, cần tối thiểu ~k-1~ lần cắt.
• Tổng số lần cắt tối thiểu là ~m - gcd(n, m)~.

Lỗi thường gặp

• Sử dụng số nguyên 32-bit thay vì 64-bit (long long)导致 overflowdo ~n, m~ lên tới ~10^{18}~.
• Không hiểu rằng tỉ lệ cắt có thể tùy ý, dẫn đến suy nghĩ sai về việc phải chia đôi đều đặn.
• Lầm tưởng rằng cần phải chia tất cả các phần bánh cho đến khi đủ ~m~ phần, trong khi chỉ cần tối thiểu hóa số thao tác để có được ~m~ phần.