Hiểu bài toán

Bài toán yêu cầu tìm số lượng viên gạch hình vuông kích thước a x a tối thiểu cần thiết để lát kín một sân bóng rổ hình chữ nhật kích thước n x m. Có thể lát thừa ra ngoài sân (mở rộng sân) nhưng không được cắt gạch. Do đó, ta cần tính số viên gạch cần thiết theo chiều dài và chiều rộng, sau đó nhân lên.

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

Cách Sử dụng phép chia lấy trần (Ceiling Division)

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

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

    // Tính số viên gạch cần thiết theo chiều dài và chiều rộng
    // Cong thuc ceil(x/y) = (x + y - 1) / y khi lam viec với số nguyên
    long long tiles_n = (n + a - 1) / a;
    long long tiles_m = (m + a - 1) / a;

    // Tính tổng số gạch và chia lấy dư
    // (x % MOD * y % MOD) % MOD để tránh tràn số
    long long total_tiles = (tiles_n % MOD) * (tiles_m % MOD) % MOD;

    cout << total_tiles << endl;

    return 0;
}

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

Đây là cách tiếp cận trực tiếp và tối ưu nhất. Ta cần tìm số viên gạch để lấp đầy chiều dài n. Vì không được cắt gạch, ta phải dùng nhiều hơn hoặc bằng n/a viên. Phép chia lấy trần ceil(n/a) được tính hiệu quả bằng (n + a - 1) / a cho số nguyên dương. Ta làm tương tự cho chiều rộng m. Kết quả cuối cùng là tích của hai số này, lấy modulo 10^9+7 như yêu cầu.

Cách Sử dụng toán tử ternary (if-else logic)

#include <bits/stdc++.h>
using namespace std;
const int N= 1E9+7;
int main(){
    long long n,m,a;
    cin>>n>>m>>a;

    // Tính số viên gạch theo chiều dài
    n = (n/a) + (n%a==0? 0:1);
    // Tính số viên gạch theo chiều rộng
    m = (m/a) + (m%a==0? 0:1);

    cout<<((n%N)*(m%N))%N;
    return 0;
}

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

Phương pháp này cũng dựa trên ý tưởng tính số viên gạch cần thiết cho mỗi chiều. Thay vì dùng công thức (x + a - 1)/a, nó chia lấy dư để kiểm tra xem có dư hay không. Nếu chia hết (n%a == 0) thì số viên là n/a. Nếu không chia hết thì cộng thêm 1 viên. Logic này tương đương với phép chia lấy trần. Tuy nhiên, cách này có thể dài dòng hơn một chút so với công thức gộp.

Cách Sử dụng hàm ceil của thư viện cmath

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

const long long MOD = 1e9 + 7;

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

    // Sử dụng hàm ceil có sẵn
    long long tiles_n = ceil((double)n / a);
    long long tiles_m = ceil((double)m / a);

    long long total_tiles = (tiles_n % MOD) * (tiles_m % MOD) % MOD;
    cout << total_tiles << endl;

    return 0;
}

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

Cách này sử dụng hàm ceil từ thư viện <cmath>. Vì n, m, a có thể lên tới 10^18, việc chuyển đổi sang kiểu double để dùng hàm ceil có thể mất độ chính xác (precision loss) đối với các số lớn. Tuy nhiên, trong hầu hết các trường hợp của bài toán này với biên 10^18, nó có thể hoạt động đúng, nhưng cách an toàn và chuẩn nhất cho số nguyên lớn vẫn là công thức (n + a - 1) / a.

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

Bài học kinh nghiệm

• Bài toán tách thành 2 chiều độc lập: số gạch theo chiều dài và số gạch theo chiều rộng.
• Vì không được cắt gạch, ta cần dùng phép chia lấy trần (ceil).
• Công thức tính ceil cho số nguyên dương: (x + y - 1) / y.
• Cần chú ý đến giới hạn dữ liệu (10^18) khi thực hiện các phép toán nhân để tránh tràn số trước khi chia lấy dư.

Lỗi thường gặp

• Sử dụng phép chia thường (n/a) sẽ cho kết quả sai nếu n không chia hết cho a.
• Lỗi tràn số (overflow) khi nhân hai số lớn (ví dụ 10^18 * 10^18) trước khi chia lấy dư. Cần phải lấy dư trước khi nhân.
• Quên xử lý trường hợp khi n hoặc m nhỏ hơn a (lúc này số gạch vẫn là 1).