Hiểu bài toán

Cho hai số nguyên dương n và m (n ≤ m). Định nghĩa hàm d(x) = x + (tổng các chữ số của x). Bắt đầu từ n, ta tạo ra một chuỗi số bằng cách liên tục áp dụng hàm d: n, d(n), d(d(n)), ... Yêu cầu đếm số lượng các số trong chuỗi này (kể từ n) mà nhỏ hơn hoặc bằng m.

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

Cách Mô phỏng trực tiếp (Simulation)

#include <iostream>
using namespace std;

int tachso(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    long long n, m, count = 0;
    cin >> n >> m;
    while (n <= m) {
        n = n + tachso(n);
        count++;
    }
    cout << count;
    return 0;
}

• Time Complexity: O(log m * (m - n)) trong trường hợp xấu nhất, nhưng thực tế nhanh hơn nhiều.
• Space Complexity: O(1)

Đây là cách giải quyết trực quan nhất. Ta bắt đầu với giá trị hiện tại là n, và trong khi nó vẫn còn nhỏ hơn hoặc bằng m, ta cập nhật nó bằng cách cộng thêm tổng các chữ số của nó và tăng biến đếm. Hàm tachso để tính tổng các chữ số. Cách này chạy khá nhanh vì tốc độ tăng của d(n) khá nhanh (ít nhất tăng 1 đơn vị, thường tăng 10-20 đơn vị), nên số bước lặp không lớn.

Cách Quy hoạch động / Đánh dấu (DP / Marking)

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

int tcs(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<bool> b(m + 1, false);
    b[n] = true;

    stack<int> st;
    st.push(n);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        if (u > m) continue;

        int v = u + tcs(u);
        if (v <= m && !b[v]) {
            b[v] = true;
            st.push(v);
        }
    }

    int ans = 0;
    for (int i = n; i <= m; i++)
        ans += b[i];

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

• Time Complexity: O(m * log m)
• Space Complexity: O(m)

Cách tiếp cận này sử dụng một mảng đánh dấu (boolean) để lưu trữ các số đã xuất hiện trong chuỗi. Nó sử dụng Stack (hoặc Queue) để duyệt các số. Từ một số u, ta tính số kế tiếp v = u + tcs(u). Nếu v chưa được đánh dấu và nằm trong giới hạn, ta đánh dấu và đẩy vào Stack. Sau khi duyệt xong, ta đếm số lượng các vị trí từ n đến m được đánh dấu. Cách này đảm bảo ta tìm được tất cả các số trong chuỗi nằm trong khoảng [n, m] nhưng tốn nhiều bộ nhớ hơn.

Cách Tối ưu Logic (Cải tiến)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int count = 0;
    while (n <= m) {
        int sum = 0;
        int temp = n;
        while (temp > 0) {
            sum += temp % 10;
            temp /= 10;
        }
        n += sum;
        count++;
    }
    cout << count << endl;
    return 0;
}

• Time Complexity: O(K * log m) - K là số lượng số sinh ra.
• Space Complexity: O(1)

Đây là phiên bản tối ưu hóa từ Solution 1. Thay vì tạo hàm riêng, ta viết trực tiếp vòng lặp tính tổng chữ số bên trong vòng lặp chính. Cấu trúc logic vẫn là mô phỏng, nhưng code gọn gàng và có thể tối ưu hóa biên dịch tốt hơn. Đây là phương pháp chuẩn và hiệu quả nhất cho ràng buộc của bài toán này.

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

Bài học kinh nghiệm

• Hàm d(x) = x + sumdigits(x) luôn tạo ra số lớn hơn x (vì sumdigits(x) >= 1 với x dương). Do đó chuỗi số luôn tăng.
• Với ràng buộc m ≤ 100000, số lượng số trong chuỗi rất nhỏ (thường < 100 số), nên phương pháp mô phỏng trực tiếp hoàn toàn đủ nhanh và an toàn.
• Cần đếm cả số khởi đầu n.

Lỗi thường gặp

• Bỏ qua số n đầu tiên trong quá trình đếm.
• Sử dụng biến có kiểu quá nhỏ (ví dụ int) nếu n và m có thể lớn hơn 2^31 (dù trong bài này nhỏ).
• Viết sai hàm tính tổng chữ số (ví dụ quên chia 10 cho số 0).