Editorial for sweshr: Chia kẹo 2

Hiểu bài toán

Cho hai số nguyên dương $N$ (số kẹo) và $M$ (số trẻ em). Cần chia $N$ viên kẹo cho $M$ người em sao cho:

1. Số kẹo của mỗi em đều khác nhau.
2. ước chung lớn nhất (GCD) của tất cả các số kẹo là lớn nhất có thể. Nếu không thể chia, in ra -1.

Phân tích:

• Để GCD là lớn nhất, hãy gọi GCD đó là $g$. Khi đó số kẹo của các em sẽ là các bội của $g$. Gọi số kẹo của các em là $x1, x2, ..., xM$. Ta có $xi = ki \cdot g$ với $ki$ là các số nguyên dương đôi một phân biệt.
• Để tổng số kẹo $N$ là tối thiểu cho trước một tập hợp $ki$, ta nên chọn các số $ki$ là $1, 2, ..., M$.
• Tổng kẹo tối thiểu cần thiết cho $M$ em là $S_{min} = 1 + 2 + ... + M = M(M+1)/2$.
• Nếu $N < S_{min}$, không thể chia, in -1.
• Nếu $N \ge S{min}$, ta có thể tìm số $g$ lớn nhất sao cho tổng kẹo không vượt quá $N$. Điều kiện là $g \cdot S{min} \le N$, hay $g \le \lfloor N / S_{min} \rfloor$.
• Bài toán quy về tìm ước số lớn nhất của $N$ không vượt quá $\lfloor N / S_{min} \rfloor$.

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

Cách Thương và Lặp (Division & Loop)

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

void solve() {
    int64 N, M;
    cin >> N >> M;

    // Tính tổng tối thiểu S = M*(M+1)/2
    // Cần kiểm tra tràn số
    __int128 min_sum = (__int128)M * (M + 1) / 2;
    if (min_sum > N) {
        cout << -1 << "\n";
        return;
    }

    int64 limit = N / (int64)min_sum;
    int64 ans = 1;

    // Tìm ước lớn nhất của N <= limit
    // Duyệt qua các ước d
    for (int64 d = 1; d * d <= N; ++d) {
        if (N % d == 0) {
            if (d <= limit) ans = max(ans, d);
            int64 other = N / d;
            if (other <= limit) ans = max(ans, other);
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(1)

Hàm số $S{min} = M(M+1)/2$ có thể rất lớn, nên dùng __int128 để tính toán và kiểm tra điều kiện ban đầu. Sau khi xác định $N \ge S{min}$, ta tính $limit = \lfloor N / S_{min} \rfloor$. Giới hạn này có thể lên tới $10^9$. Bài toán trở thành tìm ước số lớn nhất của $N$ nhỏ hơn hoặc bằng $limit$. Ta có thể duyệt các ước số của $N$ bằng cách lặp từ $1$ đến $\sqrt{N}$. Với mỗi $i$ là ước của $N$, ta có hai ước là $i$ và $N/i$. Ta cập nhật kết quả nếu ước đó nhỏ hơn hoặc bằng $limit$. Độ phức tạp là $O(\sqrt{N})$.

Cách Tối ưu Biên (Edge Case Optimization)

// Chỉ cần sửa lại phần kiểm tra limit
// Trong hàm solve() của Approach 1:

if (min_sum > N) {
    cout << -1 << "\n";
    return;
}
// Kiểm tra đặc biệt cho trường hợp limit rất lớn
// Nếu limit >= N, thì ước lớn nhất của N không vượt quá N chính là N本身.
// Tuy nhiên, code duyệt ước số O(sqrt(N)) đã xử lý tốt trường hợp này.
// Nhưng có thể tối ưu nếu limit >= sqrt(N) để giảm bước lặp.

// Code tối ưu (chỉ là nhận xét logic):
// Nếu limit >= N, không cần duyệt, in N.
// Nhưng do limit = N / S_min, và S_min >= 1, nên limit <= N.
// Nếu limit >= N, nghĩa là S_min <= 1. M=1 thì S_min=1. Nếu M=1, đáp án là N.

// Code chuẩn:
int64 ans = 1;
if (limit >= N) ans = N; // Tránh duyệt vòng lặp lớn
else {
    for (int64 d = 1; d * d <= N; ++d) {
        if (N % d == 0) {
            if (d <= limit) ans = max(ans, d);
            int64 other = N / d;
            if (other <= limit) ans = max(ans, other);
        }
    }
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(1)

Trong Approach 1, vòng lặp duyệt ước số chạy trong khoảng $O(\sqrt{N})$. Nếu $N$ nhỏ (ví dụ $N=10^9$), $\sqrt{N} \approx 31622$, vòng lặp này chạy rất nhanh. Tuy nhiên, để bài toán hoàn hảo, ta có thể thêm một bước kiểm tra nhanh: nếu $limit \ge N$, thì $N$ là ước số của $N$ và không vượt quá $limit$, nên đáp án là $N$. Thực tế, trường hợp này hiếm khi xảy ra (chỉ khi $M=1$ hoặc $M$ rất nhỏ), và code duyệt ước số chuẩn vẫn xử lý tốt nó. Approach này nhấn mạnh việc xử lý các biên của bài toán để đảm bảo độ chính xác.

Cách Tối ưu Vòng Lặp (Loop Limit)

// Thay đổi phạm vi lặp để tối ưu
void solve() {
    // ... (phần tính min_sum và limit như cũ)

    int64 ans = 1;
    // Thay vì duyệt i từ 1 đến sqrt(N), ta chỉ cần duyệt đến min(sqrt(N), limit)
    // vì nếu i > limit thì i không thể là đáp án.
    // Tuy nhiên, ta vẫn cần kiểm tra ước 'other = N/i'.
    // Nếu i > limit, thì N/i < N/limit <= min_sum.
    // Điều này không nhất thiết giúp loại bỏ i nhanh hơn.

    // Cấu trúc lặp tối ưu:
    for (int64 i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            int64 d1 = i;
            int64 d2 = N / i;
            if (d1 <= limit) ans = max(ans, d1);
            if (d2 <= limit) ans = max(ans, d2);
        }
    }
    cout << ans << "\n";
}

• Time Complexity: O(min(sqrt(N), limit))
• Space Complexity: O(1)

Phương pháp này thực chất là một biến thể của Approach 1. Điểm khác biệt nằm ở nhận thức rằng $limit$ có thể nhỏ hơn $\sqrt{N}$. Nếu $limit < \sqrt{N}$, ta có thể tối ưu vòng lặp để chỉ chạy đến $limit$ và kiểm tra các ước tương ứng. Tuy nhiên, trong hầu hết các trường hợp với $N \le 10^9$, $\sqrt{N}$ đã khá nhỏ (~31622), nên việc tối ưu này không tạo ra sự khác biệt lớn trừ khi $N$ rất lớn và $limit$ rất nhỏ. Code mẫu ở trên giữ nguyên logic duyệt $O(\sqrt{N})$ vì nó an toàn và dễ hiểu, nhưng ghi chú về việc có thể tối ưu nếu $limit$ nhỏ.

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

Bài học kinh nghiệm

• Tổng kẹo tối thiểu để chia cho $M$ người với số lượng khác nhau là $S{min} = M(M+1)/2$. Nếu $N < S{min}$, không có đáp án.
• GCD tối đa tương ứng với hệ số chung lớn nhất $g$. Với tổng kẹo cố định $N$, $g$ lớn nhất khi tổng các số chia cho $g$ là nhỏ nhất. Số chia cho $g$ tối thiểu là $1, 2, ..., M$.
• Bài toán quy về tìm ước số lớn nhất của $N$ nhỏ hơn hoặc bằng $\lfloor N / S_{min} \rfloor$.

Lỗi thường gặp

• Tràn số khi tính $M(M+1)/2$: $M$ lên tới $10^9$, nên $M(M+1)$ có thể vượt quá $2^{63}-1$. Cần dùng __int128 hoặc kiểm tra thủ công trước khi nhân.
• Bỏ qua trường hợp $M=1$: Khi đó $S_{min}=1$, $limit = N$. Ước lớn nhất của $N$ không vượt quá $N$ là $N$.
• Lỗi logic khi kiểm tra ước số: Cần kiểm tra cả $i$ và $N/i$.