Hiểu bài toán

Bài toán yêu cầu tính tích của hai số nguyên a và b (a * b) sử dụng một thuật toán đặc biệt: thuật toán nhân binary (hay còn gọi là thuật toán nhân của Nga). Thay vì thực hiện phép nhân trực tiếp, ta sẽ dựa vào việc phân tích số a theo hệ nhị phân. Nếu bit tại vị trí i của a là 1 thì ta cộng dồn giá trị của b tương ứng vào kết quả, đồng thời nhân đôi b lên sau mỗi bước. Tuy nhiên, trong các giải pháp được cung cấp, điều kiện được kiểm tra là 'a % 2 == 0' (số chẵn). Nếu a là số chẵn, ta cộng b vào kết quả. Quy trình này về cơ bản là biến đổi để tính a * b nhưng cách xử lý hơi khác biệt so với thuật toán nhân binary truyền thống (thường kiểm tra bit lẻ). Dù vậy, đây là một phương pháp tối ưu hóa phép nhân bằng cách sử dụng phép chia đôi và nhân đôi.

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

Cách Thuật toán Binary Multiplication (Dựa trên Bit)

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

int main() {
    freopen("tich.inp", "r", stdin);
    freopen("tich.out", "w", stdout);
    long long a, b;
    cin >> a >> b;
    long long kq = 0;

    while (a > 0) {
        if (a % 2 == 0) kq += b; // Nếu a chẵn, cộng b vào kết quả
        a /= 2;                   // Chia a cho 2
        b *= 2;                   // Nhân b với 2
    }

    cout << kq;
}

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

Đây là cách tiếp cận chính được sử dụng trong các giải pháp đã nộp. Nó mô phỏng phép nhân bằng cách phân tích số a. Vòng lặp 'while (a > 0)' chạy với số lần bằng số bit của a (tương đương log2(a)). Trong mỗi bước:

1. Kiểm tra tính chẵn lẻ của a (a % 2). Trong các giải pháp này, nếu a chẵn thì cộng b vào biến kết quả.
2. Chia a cho 2 (a /= 2) để duyệt qua các bit.
3. Nhân b với 2 (b *= 2) để chuẩn bị cho bit tiếp theo. Cách này thay thế phép nhân trực tiếp bằng các phép cộng, dịch bit (chia/ nhân đôi), giúp tính toán nhanh hơn và tránh tràn số nếu dữ liệu phù hợp (cần dùng kiểu dữ liệu lớn như long long).

Cách Brute Force (Cộng lặp)

// Pseudocode giải thích
long long kq = 0;
for(int i = 0; i < b; i++) {
    kq += a;
}
cout << kq;

• Time Complexity: O(n) (Vô cùng lớn, không khả thi)
• Space Complexity: O(1)

Đây là cách tiếp cận ngây thơ nhất: lấy a cộng lại b lần. Nếu b lên tới 10^9 hoặc lớn hơn, vòng lặp này sẽ chạy quá giới hạn thời gian cho phép (Time Limit Exceeded). Các giải pháp đã nộp đã tránh hoàn toàn cách này.

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

Bài học kinh nghiệm

• Phép nhân có thể thực hiện bằng cách sử dụng các phép toán cơ bản như cộng và dịch bit (nhân/chia đôi).
• Kiểu dữ liệu 'long long' (hoặc 'll') là bắt buộc để tránh tràn số (overflow) khi a hoặc b có giá trị lớn.
• Việc nhập xuất qua file (freopen) là yêu cầu phổ biến trong các kỳ thi lập trình thi đấu.

Lỗi thường gặp

• Sử dụng kiểu 'int' thay vì 'long long' dẫn đến tràn số khi a và b lớn.
• Viết sai điều kiện lặp: vòng lặp phải là 'while (a > 0)' hoặc 'while (a != 1)' (nếu bắt đầu từ a >= 1). Nếu dùng 'while (a != 0)' khi a bắt đầu bằng 0 thì sẽ không chạy.
• Quên cập nhật giá trị của a (phải chia cho 2) và b (phải nhân đôi) sau mỗi bước lặp.