Đếm số hình vuông trong hình chữ nhật L×B C++

Cho hình chữ nhật chiều dài L, chiều rộng B (L ≥ B). Đếm tổng số hình vuông con (các kích thước) có trong hình chữ nhật.

Ví dụ minh họa

Ví dụ 1:

• Input: L = 4, B = 2
• Output: 11
• Giải thích: 8 vuông 1×1, 3 vuông 2×2. Tổng = 11.

Ví dụ 2:

• Input: L = 3, B = 3
• Output: 14
• Giải thích: 9 vuông 1×1, 4 vuông 2×2, 1 vuông 3×3. Tổng = 14.

Công thức toán học

Với hình vuông B×B: số vuông = 1² + 2² + ... + B² = B(B+1)(2B+1)/6.

Với mỗi cột thêm ra (L-B cột), thêm: B + (B-1) + ... + 1 = B(B+1)/2 vuông.

Tổng cộng: B(B+1)(2B+1)/6 + (L-B) × B(B+1)/2

Mã nguồn C++

#include <iostream>
using namespace std;

int numofSquares(int l, int b) {
    int squares = 0;
    // Vuông trong vùng BxB
    for (int i = 1; i <= b; i++) {
        squares += i * i;
    }
    // Vuông thêm từ (L-B) cột mở rộng
    squares += (l - b) * b * (b + 1) / 2;
    return squares;
}

int main() {
    int length = 5, breadth = 4;
    cout << "So hinh vuong: " << numofSquares(length, breadth);
    return 0;
}

Kết quả chạy chương trình

So hinh vuong: 40

Công thức đóng O(1)

long long countSquares(long long L, long long B) {
    if (L < B) swap(L, B);
    // B(B+1)(2B+1)/6 + (L-B)*B(B+1)/2
    long long term1 = B * (B + 1) * (2 * B + 1) / 6;
    long long term2 = (L - B) * B * (B + 1) / 2;
    return term1 + term2;
}

Độ phức tạp

Kiểm tra ví dụ

• L=4, B=2: term1 = 2×3×5/6 = 5, term2 = 2×2×3/2 = 6 → 11 ✓
• L=3, B=3: term1 = 3×4×7/6 = 14, term2 = 0 → 14 ✓
• L=5, B=4: term1 = 4×5×9/6 = 30, term2 = 1×4×5/2 = 10 → 40 ✓

Lưu ý

• Dùng long long tránh tràn số (L,B ≤ 10⁹).
• Đảm bảo L ≥ B (hoặc swap).