Hiểu bài toán

Bài toán yêu cầu tính kết quả của phép nhân một số lớn (đại diện bằng chuỗi ký tự số) với số 2, lặp lại t lần. Ban đầu, ta có một số nguyên lớn S (dưới dạng chuỗi) và một số nguyên dương t. Sau mỗi lần lặp, S được nhân với 2. Cần in ra kết quả cuối cùng sau t lần nhân. Ví dụ, nếu S = "12" và t = 2, kết quả là 12 * 2 * 2 = 48. Do S có thể rất lớn, không thể lưu trữ trong các kiểu dữ liệu nguyên cơ bản mà cần xử lý dưới dạng chuỗi.

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

Cách Nhân lớn với số nguyên nhỏ (tối ưu)

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

string nhan2(string s) {
    string tmp = "";
    int so_nho = 0;
    for(int i = s.size()-1; i >= 0; i--) {
        int temp = (int(s[i]) - 48) * 2 + so_nho;
        tmp = to_string(temp % 10) + tmp;
        so_nho = temp / 10;
    }
    if (so_nho > 0) tmp = to_string(so_nho) + tmp;
    return tmp;
}

int main() {
    string s;
    int t;
    cin >> s >> t;
    if(s == "0") {
        cout << 0;
        return 0;
    }
    for(int i = 0; i < t; i++) {
        s = nhan2(s);
    }
    cout << s;
    return 0;
}

• Time Complexity: O(N * t)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất để giải quyết bài toán. Nó tận dụng việc chỉ nhân với số 2, phép toán cơ bản. Với mỗi lần nhân, ta duyệt từ chữ số cuối lên chữ số đầu của chuỗi, thực hiện nhân từng chữ số với 2 và cộng với phần nhớ (carry) từ phép tính trước đó. Nếu có phần nhớ cuối cùng, ta thêm nó vào đầu chuỗi. Do độ dài chuỗi tăng chậm (tối đa khoảng N + log2(t) chữ số), độ phức tạp thời gian là O(N * t), đủ nhanh cho các dữ liệu thi đấu thông thường (N, t nhỏ, ví dụ N <= 1000, t <= 1000).

Cách Nhân lớn với số lớn (General)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string nhan(string s, string n) {
    int len1 = s.size(), len2 = n.size();
    vector<int> res(len1 + len2, 0);

    for (int i = len1 - 1; i >= 0; i--)
        for (int j = len2 - 1; j >= 0; j--)
            res[i + j + 1] += (s[i] - '0') * (n[j] - '0');

    for (int i = len1 + len2 - 1; i > 0; i--) {
        res[i - 1] += res[i] / 10;
        res[i] %= 10;
    }

    string kq;
    int i = 0;
    while (i < res.size() && res[i] == 0) i++;
    if (i == res.size()) return "0";
    for (; i < res.size(); i++) kq.push_back(res[i] + '0');
    return kq;
}

int main() {
    string s, t_str;
    cin >> s >> t_str;
    // Vòng lặp t lần hoặc nhanh hơn nếu t là số
    // Code mẫu này chỉ minh họa hàm nhân chung
    // Trong bài này có thể thay t_str bằng "2" và lặp lại
    return 0;
}

• Time Complexity: O(N^2 * t)
• Space Complexity: O(N)

Đây là cách lập trình tổng quát cho phép nhân hai số lớn, sử dụng mảng phụ để lưu kết quả từng cột. Mỗi phép nhân thực hiện phép nhân từng chữ số (thuật toán cơ bản của lớp 3). Trong bài toán này, ta lặp lại phép nhân này t lần. Tuy nhiên, do chỉ nhân với số 2, cách này hơi cồng kềnh và chậm hơn so với cách tối ưu cho số 2 (Approach 1). Độ phức tạp O(N^2 * t) là hơi cao nếu dùng cho việc nhân 2 lặp lại.

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

Bài học kinh nghiệm

• Bài toán này về cơ bản là tính 2^t * S.
• Vì số lượng lần nhân t có thể lớn, nhưng độ dài số tăng chậm, cách nhân trực tiếp từng bước là khả thi.
• Chuỗi ký tự là cấu trúc dữ liệu duy nhất có thể chứa số rất lớn.

Lỗi thường gặp

• Sử dụng các kiểu dữ liệu số nguyên (int, long long) để lưu số ban đầu hoặc kết quả trung gian => Bị tràn số (overflow).
• Lỗi logic khi tính toán nhớ (carry) dẫn đến kết quả sai.
• Xử lý sai trường hợp input số ban đầu là 0.