Editorial for ptit049: Tô màu 1

Hiểu bài toán

Đề bài yêu cầu đếm số cách tô màu K ô trong một bảng M hàng x N cột sao cho các ô được tô tạo thành một hình chữ nhật (đặc biệt là hình vuông nếu côt). Số cách tô màu tương ứng với số vị trí đặt một hình chữ nhật có diện tích K vào trong bảng MxN.

Cụ thể, ta cần chọn một hình chữ nhật có kích thước a x b (với a là số hàng, b là số cột) sao cho a * b = K. Với mỗi kích thước có thể đặt vào bảng MxN, số cách đặt là (M - a + 1) * (N - b + 1) (nếu a <= M và b <= N).

Do M, N, K có thể lên tới 10^9, ta không thể duyệt qua tất cả các hình chữ nhật. Tuy nhiên, số lượng ước của K (và do đó số lượng cặp (a, b)) là khá nhỏ (khoảng ~sqrt(K)), cho phép ta duyệt qua các ước của K để tính toán.

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

Cách Duyệt các ước của K

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

using i128 = __int128_t;

void print_i128(i128 x){
    if(x==0){ cout<<0; return; }
    if(x<0){ cout<<'-'; x=-x; }
    string s;
    while(x){ s.push_back('0'+(int)(x%10)); x/=10; }
    reverse(s.begin(), s.end());
    cout<<s;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long M,N,K;
    if(!(cin>>M>>N>>K)){ return 0; }
    if(K==0){ cout<<0; return 0; }

    i128 ans = 0;
    // Duyệt a từ 1 đến sqrt(K)
    for(long long a = 1; a*a <= K; ++a){
        if(K % a) continue;
        long long b = K / a;

        // Trường hợp a là số hàng, b là số cột
        if(a <= M && b <= N){
            ans += (i128)(M - a + 1) * (N - b + 1);
        }
        // Trường hợp a là số cột, b là số hàng (nếu a != b)
        if(a != b && b <= M && a <= N){
            ans += (i128)(M - b + 1) * (N - a + 1);
        }
    }
    print_i128(ans);
    return 0;
}

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

Giải pháp này dựa trên việc nhận thấy rằng một hình chữ nhật diện tích K được xác định bởi hai kích thước a và b sao cho a * b = K. Để đếm số cách đặt hình chữ nhật này vào bảng MxN, ta cần tìm tất cả các cặp (a, b).

Thay vì duyệt tất cả các cặp (a, b) (vốn không khả thi do K lớn), ta chỉ cần duyệt qua các ước của K. Vì a * b = K, nên a là một ước của K và b = K / a.

Thuật toán:

1. Duyệt a từ 1 đến sqrt(K).
2. Nếu a chia hết cho K, ta có một cặp (a, K/a).
3. Xét a làm số hàng, K/a làm số cột: Nếu a <= M và K/a <= N, số cách đặt là (M - a + 1) * (N - K/a + 1).
4. Xét K/a làm số hàng, a làm số cột: Nếu K/a <= M và a <= N, số cách đặt là (M - K/a + 1) * (N - a + 1). (Chỉ xét khi a != K/a để tránh đếm trùng).
5. Cộng dồn vào kết quả.

Vì K có thể lên tới 10^9, số lượng ước cần duyệt là khoảng 31622, hoàn toàn chấp nhận được. Kết quả có thể vượt quá 64-bit integer (do M, N, K lớn), do đó cần sử dụng __int128 (nếu compiler hỗ trợ) hoặc thư viện big integer để lưu trữ và in kết quả.

Cách Tối ưu hóa nhập xuất (C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;

__int128 print (__int128 a) {
    // Hàm in số lớn (logic tương tự trong code gốc)
    string s = "";
    if (a == 0) return 0;
    while (a != 0) {
        s += (char)(a % 10 + 48);
        a /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s;
    return 0;
}

int main() {
    ll mm, nn, kk;
    cin >> mm >> nn >> kk;
    __int128 m = mm, n = nn, k = kk;
    if (m == 0 || n == 0 || k == 0) {
        cout << 0;
        return 0;
    }
    __int128 ans = 0;
    for (__int128 i = 1; i * i <= k; ++i) {
        if (k % i == 0) {
            __int128 j = k / i;
            if (i <= m && j <= n) {
                ans += (m - i + 1) * (n - j + 1);
            }
            if (i != j && j <= m && i <= n) {
                ans += (m - j + 1) * (n - i + 1);
            }
        }
    }
    print(ans);
    return 0;
}

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

Đây là phiên bản tối ưu hóa của Approach 1, sử dụng trực tiếp kiểu dữ liệu __int128 cho các biến đầu vào và vòng lặp để tránh các lỗi overflow tiềm ẩn khi thực hiện các phép nhân trên số lớn. Code cũng bao hàm logic xử lý in số lớn vì chuẩn C++ không hỗ trợ in __int128 trực tiếp trên hầu hết các trình biên dịch. Logic thuật toán hoàn toàn giống với Approach 1.

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

Bài học kinh nghiệm

• Bài toán quy về đếm số cách đặt một hình chữ nhật diện tích K vào bảng MxN.
• Số lượng vị trí đặt hình chữ nhật a x b là (M - a + 1) * (N - b + 1).
• Vì K lớn (10^9), ta không thể duyệt tất cả a, b mà chỉ duyệt các ước của K (vòng lặp chạy đến sqrt(K)).
• Kết quả có thể rất lớn, cần sử dụng số nguyên lớn (__int128 hoặc BigInt).

Lỗi thường gặp

• Overflow số nguyên khi tính toán: Khi M, N, K lên tới 10^9, phép nhân (M - a + 1) * (N - b + 1) có thể vượt quá giới hạn của long long (khoảng 10^18). Cần dùng __int128.
• Xử lý sai trường hợp hình vuông: Khi a = b (K là số chính phương), nếu không kiểm tra if (i != j), ta sẽ đếm vị trí đặt vuông đó 2 lần (một lần với a là chiều ngang, một lần với a là chiều dọc).
• Quên kiểm tra biên: Phải đảm bảo a <= M và b <= N (và ngược lại) trước khi tính số cách đặt, nếu không sẽ ra số âm hoặc kết quả sai.
• Xử lý K = 0: Đề bài cho phép K = 0. Nếu K = 0, số cách tô là 0 (theo logic bài toán và các giải pháp tham chiếu).