Hiểu bài toán

Đề bài yêu cầu cắt một hình chữ nhật có kích thước h x w thành các hình vuông có cùng kích thước sao cho cạnh của các hình vuông đó là lớn nhất có thể. Chúng ta cần tìm số lượng hình vuông lớn nhất này sau khi cắt. Ví dụ, với h = 6 và w = 9, ta có thể cắt thành các hình vuông 3x3. Kích thước này là lớn nhất vì nếu dùng 6x6 thì không chia được w=9, hoặc 4x4 không chia được h=6. Số lượng hình vuông thu được sẽ là (h / cạnhhìnhvuông) * (w / cạnhhìnhvuông).

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

Cách Tìm ước chung lớn nhất (GCD)

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

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

    int t;
    cin >> t;
    while (t--) {
        long long a, b;
        cin >> a >> b;
        long long g = gcd(a, b);
        cout << (a / g) * (b / g) << "\n";
    }
}

• Time Complexity: O(log(min(h, w))) cho mỗi test case
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất. Kích thước cạnh hình vuông lớn nhất mà có thể cắt ra từ hình chữ nhật h x w chính là ước chung lớn nhất (GCD) của h và w. Lý do là nếu cạnh hình vuông là 'x', thì 'x' phải chia hết cho cả h và w (thực chất là h và w phải chia hết cho x), tức là x là ước của cả hai. Để 'x' là lớn nhất, nó phải là GCD(h, w). Sau đó, số lượng hình vuông được tính bằng cách chia chiều dài và chiều rộng cho kích thước cạnh này rồi nhân lên: (h/g) * (w/g).

Cách Duyệt tìm ước số lớn nhất (Brute Force)

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int h, w;
        cin >> h >> w;
        int max_sq_size = 1;
        // Duyệt từ min(h, w)下降 về 1
        for (int i = min(h, w); i >= 1; i--) {
            if (h % i == 0 && w % i == 0) {
                max_sq_size = i;
                break;
            }
        }
        cout << (long long)(h / max_sq_size) * (w / max_sq_size) << endl;
    }
    return 0;
}

• Time Complexity: O(min(h, w)) cho mỗi test case
• Space Complexity: O(1)

Phương pháp này tìm kích thước cạnh lớn nhất bằng cách duyệt từ kích thước nhỏ nhất của hai chiều (min(h, w)) giảm dần về 1. Số đầu tiên chia hết cả h và w chính là GCD. Phương pháp này đúng nhưng chậm hơn nhiều so với dùng thuật toán Euclid, đặc biệt với các số lớn (dù đề bài giới hạn 1000, nhưng về mặt lý thuyết là kém hiệu quả).

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

Bài học kinh nghiệm

• Kích thước cạnh hình vuông lớn nhất bằng GCD(h, w).
• Số lượng hình vuông = (h / GCD) * (w / GCD).

Lỗi thường gặp

• Quên dùng kiểu dữ liệu lớn (long long) nếu h và w có giá trị lớn (trong bài này 1000 thì int vẫn ổn nhưng để an toàn nên dùng long long cho phép nhân).
• Sử dụng các thư viện không cần thiết hoặc sai cú pháp _gcd trong các trình biên dịch không hỗ trợ GNU extensions (trong khi _gcd là chuẩn trong GCC).