Số Demlo (Demlo Number) - Bình phương của 11...1 trong C++

Giới thiệu

Số Demlo là bình phương của các số chỉ chứa chữ số 1: 1², 11², 111², 1111², ...

Đặc điểm: Kết quả có dạng đối xứng 123...n...321

Quy luật

Mã nguồn hoàn chỉnh

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

string getDemloNumber(string str) {
    int len = str.length(); // Số lượng chữ số 1
    string demlo = "";
    
    // Phần tăng: 1, 2, 3, ..., len
    for (int i = 1; i <= len; i++) {
        demlo += char('0' + i);
    }
    
    // Phần giảm: len-1, ..., 3, 2, 1
    for (int i = len - 1; i >= 1; i--) {
        demlo += char('0' + i);
    }
    
    return demlo;
}

int main() {
    string str = "1111111"; // 7 chữ số 1
    cout << getDemloNumber(str) << endl;
    return 0;
}

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

1234567654321

Giới hạn của phương pháp này

Quy luật 123...n...321 chỉ đúng khi n ≤ 9 (vì chữ số chỉ 0-9).

Với 10 chữ số 1: 1111111111² = 1234567900987654321 (không đối xứng đơn giản).

Phương pháp chung cho mọi n (Big Integer)

string multiplyStrings(string a, string b) {
    int n = a.size(), m = b.size();
    vector res(n + m, 0);
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int mul = (a[i] - '0') * (b[j] - '0');
            int sum = mul + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }
    
    string result;
    for (int num : res) {
        if (!(result.empty() && num == 0)) result += char(num + '0');
    }
    return result.empty() ? "0" : result;
}

string getDemloBigInteger(string ones) {
    return multiplyStrings(ones, ones);
}

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

• Phương pháp quy luật (n≤9): O(n) thời gian, O(n) không gian
• Phương pháp nhân chuỗi (big integer): O(n²) thời gian, O(n) không gian

Kết luận

Số Demlo là ví dụ đẹp của quy luật số học. Đối với n ≤ 9, có thể sinh kết quả trực tiếp theo mẫu 123...n...321. Với n lớn, cần nhân số lớn (big integer multiplication).