Hiểu bài toán

Bài toán yêu cầu chia n bạn nam và m bạn nữ thành nhiều tổ nhất có thể sao cho:

1. Các tổ có số lượng thành phần bằng nhau.
2. Số lượng nam và nữ trong mỗi tổ là như nhau giữa các tổ.
3. Mỗi học sinh thuộc đúng 1 tổ. Điều này có nghĩa là số tổ (k) phải là ước chung của n và m. Để tối đa hóa số lượng tổ, ta cần chọn ước chung lớn nhất (gcd) của n và m. Khi đó:

• Số tổ = gcd(n, m)
• Số nam mỗi tổ = n / gcd(n, m)
• Số nữ mỗi tổ = m / gcd(n, m)

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

Cách Brute Force (Tìm ước chung lớn nhất bằng cách duyệt)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;

    long long k = min(n, m);
    while (k > 0) {
        if (n % k == 0 && m % k == 0) {
            break;
        }
        k--;
    }

    cout << k << "\n";
    cout << n / k << " " << m / k;

    return 0;
}

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

Phương pháp này tìm ước chung lớn nhất bằng cách duyệt từ số nhỏ hơn của n và m giảm dần đến 1. Số đầu tiên chia hết cho cả n và m chính là ước chung lớn nhất. Tuy nhiên, với n, m lên tới 10^15, độ phức tạp O(min(n, m)) là quá lớn và không thể chạy kịp.

Cách Euclidean Algorithm (Thuật toán Euclid)

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    long long n, m;
    cin >> n >> m;

    long long k = gcd(n, m);

    cout << k << "\n";
    cout << n / k << " " << m / k;

    return 0;
}

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

Đây là phương pháp chuẩn để tính ước chung lớn nhất. Thuật toán Euclid dựa trên tính chất gcd(a, b) = gcd(b, a % b). Với n, m lên tới 10^15, độ phức tạp logarithmic là hoàn toàn khả thi. Với 10^15, chỉ mất khoảng 50-60 bước tính toán.

Cách Built-in GCD Function (Hàm có sẵn)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;

    long long k = __gcd(n, m);

    cout << k << "\n";
    cout << n / k << " " << m / k;

    return 0;
}

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

Phương pháp này sử dụng hàm _gcd() có sẵn trong trình biên dịch GCC. Đây là cách ngắn gọn và hiệu quả nhất. Hàm này cũng sử dụng thuật toán Euclid hoặc biến thể优化 của nó. Tuy nhiên, cần lưu ý _gcd là extension không chuẩn, nhưng thường được hỗ trợ trong lập trình thi đấu.

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

Bài học kinh nghiệm

• Vấn đề có thể quy về tìm ước chung lớn nhất (GCD) của hai số n và m.
• Số tổ tối đa bằng GCD(n, m), và mỗi tổ sẽ có n/GCD(n, m) nam và m/GCD(n, m) nữ.
• Với giới hạn 10^15, cần sử dụng thuật toán có độ phức tạp logarithmic như Euclid.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int thay cho long long sẽ gây tràn số với n, m lên tới 10^15.
• Phương pháp duyệt từ 1 đến min(n, m) để tìm ước chung lớn nhất sẽ gây timeout với dữ liệu lớn.
• Quên xử lý trường hợp n hoặc m bằng 0 (dù đề bài cho n, m >= 1).