Hiểu bài toán

Bài toán yêu cầu tính số lượng ô cửa sổ hình vuông có độ dài K có thể đặt vào một bức tường hình vuông có độ dài N. Các ô cửa sổ có thể đặt sát nhau và không được chồng lên nhau. Ta cần tìm số lượng tối đa các ô có thể đặt vào. Với mỗi chiều, số lượng ô có thể đặt được là N chia lấy nguyên cho K (tức là floor(N/K)). Vì hình vuông nên số lượng ô trong cả bức tường sẽ là (N/K)*(N/K).

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

Cách Phương pháp chia lấy nguyên

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        long long n,k;
        cin>>n>>k;
        cout<<(n/k)*(n/k)<<endl;
    }
    return 0;
}

• Time Complexity: O(1) cho mỗi test case, tổng O(T)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan và tối ưu nhất. Với mỗi chiều của bức tường (có độ dài N), số lượng ô cửa sổ (có độ dài K) có thể đặt dọc theo chiều đó là số nguyên lớn nhất không vượt quá N/K, được tính bằng phép chia lấy nguyên n/k. Vì bức tường là hình vuông và các ô cũng là hình vuông, số lượng ô tối đa có thể đặt vào là tích của số ô theo chiều ngang và số ô theo chiều dọc, tức là (n/k)*(n/k).

Cách Sử dụng phép toán số học

#include <iostream>
using namespace std;
typedef long long ll; 

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--){
        int n, k; cin >> n >> k;
        cout << (long long) (n/k) * (n/k) << "\n";
    } 
}

• Time Complexity: O(1) cho mỗi test case
• Space Complexity: O(1)

Cách tiếp cận này tương tự như cách đầu tiên, sử dụng phép chia lấy nguyên để xác định số lượng ô có thể đặt trên mỗi hàng và mỗi cột. Việc khai báo long long hoặc cast (long long) đảm bảo rằng phép nhân không bị tràn số nếu kết quả (n/k) lớn (dù trong ràng buộc của bài này n <= 10^5 và k >= 1 thì n/k <= 10^5, phép nhân (10^5)*(10^5) = 10^10 vẫn nằm trong giới hạn của long long).

Cách Kiểm tra điều kiện K > N

#include<iostream>
int main(){
    int t;
    std::cin>>t;
    for(int test = 0;test<t;test++){
        long long n;
        int k;
        std::cin>>n>>k;
        std::cout<<(n/k)*(n/k)<<std::endl;
    }
    return 0;
}

• Time Complexity: O(1) cho mỗi test case
• Space Complexity: O(1)

Approach này sử dụng cùng logic toán học. Khi K > N, phép chia n/k sẽ trả về 0, và 0*0 = 0. Đây là kết quả đúng (không thể đặt ô nào). Do đó, không cần viết thêm nhánh if để kiểm tra K > N. Logic chia lấy nguyên đã xử lý đúng cả trường hợp này.

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

Bài học kinh nghiệm

• Bài toán có thể biến về bài toán toán học đơn giản: tính số lượng tối đa các hình vuông KxK có thể xếp vào hình vuông NxN.
• Số lượng ô theo mỗi chiều là floor(N / K) (số nguyên lớn nhất không vượt quá N/K).
• Tổng số ô là tích của số lượng ô theo chiều ngang và chiều dọc.

Lỗi thường gặp

• Lỗi tràn số (integer overflow): Nếu sử dụng int cho kết quả (n/k)*(n/k) trong khi n lớn, kết quả có thể vượt quá 2^31-1. Cần sử dụng long long.
• Quên xử lý trường hợp K > N: Logic chia lấy nguyên tự xử lý trường hợp này (kết quả là 0), nhưng nếu implement theo cách khác (ví dụ dùng vòng lặp) cần đảm bảo không vào vòng lặp vô hạn.