Số Deserium (Deserium Number) trong C++

Giới thiệu

Số Deserium (còn gọi là Disarium number) là số mà tổng các chữ số mũ theo vị trí (từ trái sang phải, bắt đầu từ 1) bằng chính số đó.

Định nghĩa

Số n có k chữ số: d₁d₂...dₖ

n là Deserium nếu: d₁¹ + d₂² + d₃³ + ... + dₖᵏ = n

Ví dụ

135: 1¹ + 3² + 5³ = 1 + 9 + 125 = 135 ✓

89: 8¹ + 9² = 8 + 81 = 89 ✓

175: 1¹ + 7² + 5³ = 1 + 49 + 125 = 175 ✓

518: 5¹ + 1² + 8³ = 5 + 1 + 512 = 518 ✓

Mã nguồn hoàn chỉnh

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

int getDigitsCount(int n) {
    int count = 0;
    do {
        count++;
        n /= 10;
    } while (n != 0);
    return count;
}

bool isDeseriumNumber(int n) {
    int original = n;
    int digits = getDigitsCount(n);
    int sum = 0;
    
    // Xử lý từ chữ số cuối (hàng đơn vị) về đầu
    // Vì lũy thừa phụ thuộc vào vị trí từ trái, ta cần xử lý ngược
    vector digits_vec;
    int temp = n;
    while (temp > 0) {
        digits_vec.push_back(temp % 10);
        temp /= 10;
    }
    reverse(digits_vec.begin(), digits_vec.end());
    
    for (int i = 0; i < digits_vec.size(); i++) {
        sum += pow(digits_vec[i], i + 1);
    }
    
    return sum == original;
}

int main() {
    vector test = {135, 89, 175, 518, 123, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    cout << "Cac so Deserium nho hon 1000:" << endl;
    for (int i = 1; i < 1000; i++) {
        if (isDeseriumNumber(i)) {
            cout << i << " ";
        }
    }
    cout << endl;
    
    return 0;
}

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

Cac so Deserium nho hon 1000:
1 2 3 4 5 6 7 8 9 89 135 175 518 598 

Danh sách số Deserium (OEIS A032799)

1, 2, 3, 4, 5, 6, 7, 8, 9, 89, 135, 175, 518, 598, 1306, 1676, 2427, 2646798, ...

Chỉ có 19 số Deserium đã biết (lớn nhất có 20 chữ số).

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

• Thời gian: O(d²) - d là số chữ số (do pow và chuyển đổi)
• Không gian: O(d) - lưu các chữ số

Cải tiến: Không dùng vector

bool isDeseriumOptimized(int n) {
    int original = n;
    int digits = 0, temp = n;
    while (temp) { digits++; temp /= 10; }
    
    int sum = 0;
    temp = n;
    // Xử lý từ phải sang trái, nhưng cần lũy thừa từ trái sang phải
    // Cách 1: lưu vào mảng
    // Cách 2: đệ quy
    return false; // Cần triển khai đầy đủ
}

Kết luận

Số Deserium là dãy số thú vị trong lý thuyết số. Có số lượng hữu hạn (chỉ 19 số đã biết). Bài tập tốt để luyện tập xử lý chữ số và lũy thừa.