Hiểu bài toán

Bài toán yêu cầu tính bình phương của một số S, trong đó S là một số chỉ bao gồm toàn chữ số 1 và có n chữ số (ví dụ: n=3 thì S=111). Với n nhỏ (≤9), ta có thể quan sát thấy quy luật: 11²=121, 111²=12321, 1111²=1234321... Tuy nhiên, với n lớn hơn 9, quy luật này thay đổi do các số bị tràn (carry) khi cộng các số 10, 100,... Do đó, ta cần một phương pháp tính toán chính xác cho mọi n. Nhu cầu là in ra kết quả chính xác dù n có thể lên tới 1,000,000.

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

Cách Mô phỏng nhân chéo (Cross Multiplication)

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

static unsigned char a[2000005]; // Mảng lưu kết quả

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

    int n;
    cin >> n;

    long long carry = 0;
    int len = 0;

    // Tính giá trị của các chữ số từ trái sang phải
    // Phần tăng dần: 1, 2, ..., n
    for(int i=1;i<=n;i++){
        long long total = carry + i;
        a[len++] = total % 10;
        carry = total / 10;
    }

    // Phần giảm dần: n-1, ..., 1
    for(int i=n-1;i>=1;i--){
        long long total = carry + i;
        a[len++] = total % 10;
        carry = total / 10;
    }

    // Xử lý phần nhớ cuối cùng
    while(carry){
        a[len++] = carry % 10;
        carry /= 10;
    }

    // In kết quả (lật ngược lại vì mảng lưu từ LSB)
    for(int i=len-1;i>=0;i--) cout << char(a[i]+'0');
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là phương pháp hiệu quả nhất dựa trên quan sát toán học. Biểu thức bình phương của S có thể suy ra bằng cách nhân số 111...111 với chính nó. Khi thực hiện phép nhân này, các tích phần tử sẽ tạo thành một chuỗi số có dạng hình thoi: bắt đầu tăng dần từ 1 đến n, rồi giảm dần từ n-1 về 1. Ví dụ với n=3: các tích là 1, 2, 3, 2, 1. Ta chỉ cần tạo một mảng chứa các số này (không quan tâm đến vị trí cột), rồi thực hiện cộng dồn nhớ từ phải sang trái (từ các số có trọng số thấp lên cao). Vòng lặp đầu tiên tạo ra chuỗi 1, 2, ..., n và xử lý nhớ. Vòng lặp thứ hai thêm chuỗi n-1, ..., 1 vào đuôi và tiếp tục xử lý nhớ. Các giá trị trong mảng có thể lớn (lớn hơn 9), nên ta phải chia lấy dư để tách ra các chữ số, và cộng phần nhớ vào các vị trí tiếp theo.

Cách Dùng vector BigInt

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

int32_t main() {
    ios_base :: sync_with_stdio( false );
    cin.tie( nullptr );

    int n;
    cin >> n;

    // Tạo mảng a lưu kết quả, kích thước đủ lớn
    vector<int> a( 2*n+5, 0 );

    // Gán giá trị theo quy luật: a[k] = min(k+1, 2*n - k - 1)
    // Tạo ra dãy 1, 2, ..., n-1, n, n-1, ..., 1
    for(int k = 0; k <= 2*n-2; k ++ ) {
        if( k <= n-1 ) 
            a[k] = k+1;
        else 
            a[k] = 2*n-k-1;
    }

    // Xử lý nhớ
    for( int i = 0; i <= 2*n-2; i ++ ) 
    if( a[i] >= 10 ) {
        int r = a[i]/10;
        a[i] %= 10;
        a[i+1] += r;
    } 

    // In kết quả từ chữ số cuối lên đầu
    string res;
    for(int i = 2*n-2; i >= 0; i -- ) 
        res.push_back( char( '0'+a[i] ) );

    cout << res << "\n";
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này cũng dựa trên quan sát quy luật 1, 2, ..., n, ..., 2, 1. Nó tạo mảng chứa các giá trị này trước bằng công thức toán học. Sau đó, nó duyệt qua mảng để thực hiện 'nén' các số lớn hơn 10 (xử lý nhớ). Phương pháp này khác với cách trên ở chỗ nó tạo xong toàn bộ dãy số trước rồi mới xử lý nhớ sau, trong khi cách trên vừa tạo vừa xử lý nhớ để tối ưu bộ nhớ hơn.

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

Bài học kinh nghiệm

• Bình phương số 11...1 (n chữ số) cho kết quả có dạng đối xứng: tăng dần 1->n rồi giảm dần n-1->1 ở các chữ số (chưa xử lý nhớ), không phụ thuộc vào số lượng chữ số 1.
• Vì n có thể lên tới 1,000,000, kết quả có thể có khoảng 2,000,000 chữ số. Do đó, không thể sử dụng các kiểu dữ liệu số nguyên chuẩn (long long), mà phải dùng mảng/đại số boolean hoặc mô phỏng trực tiếp trên chuỗi.
• Hai cách tiếp cận chính đều dựa trên mô phỏng thuật toán nhân chéo (cross multiplication) nhưng khác nhau ở thứ tự thực hiện tính toán và xử lý nhớ.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu số nguyên cố định (int, long long)导致 tràn số (overflow) khi n > 9 hoặc n lớn.
• Lỗi phân bổ bộ nhớ: mảng quá nhỏ không đủ chứa kết quả.
• Lỗi logic in ấn: in sai thứ tự (phải in từ chữ số cuối lên đầu hoặc ngược lại tùy cách lưu trữ).