Hiểu bài toán

Bài toán yêu cầu tìm số lượng các số nguyên dương x (0 < x < 10^9) thỏa mãn phương trình x = b * S(x)^a + c, trong đó a, b, c là các hằng số cho trước và S(x) là tổng các chữ số của x. Ta cần đếm số lượng nghiệm.

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

Cách Brute Force theo tổng chữ số (S(x))

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

int sumDigits(long long n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int a;
    long long b, c;
    if (!(cin >> a >> b >> c)) return 0;

    int ans = 0;
    // Vòng lặp chạy từ s = 1 đến 81 (tối đa tổng chữ số của số < 10^9)
    for (int s = 1; s <= 81; ++s) {
        long long pw = 1;
        for (int i = 0; i < a; ++i) pw *= s;

        long long x = b * pw + c;

        // Kiểm tra điều kiện: x phải dương, nhỏ hơn 10^9 và tổng chữ số bằng s
        if (x > 0 && x < 1000000000LL) {
            if (sumDigits(x) == s) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(1) (vì số lần lặp là hằng số ~81 * a)
• Space Complexity: O(1)

Phương pháp này dựa trên nhận định rằng tổng chữ số S(x) của một số x < 10^9 không thể vượt quá 81 (9 chữ số * 9). Do đó, thay vì duyệt x, ta duyệt qua các giá trị tổng chữ số s có thể có (từ 1 đến 81). Với mỗi s, ta tính giá trị x theo công thức x = b * s^a + c. Sau đó, ta chỉ cần kiểm tra xem giá trị x này có thỏa mãn điều kiện (0 < x < 10^9) và tổng chữ số của nó có đúng bằng s hay không. Nếu có, đó là một nghiệm. Độ phức tạp là hằng số vì số lần lặp rất nhỏ.

Cách Tối ưu hóa tính toán

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

int sumDigits(long long x) {
    int s = 0;
    while (x > 0) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

long long power(int base, int exp) {
    long long res = 1;
    for (int i = 0; i < exp; ++i) res *= base;
    return res;
}

int main() {
    int a;
    long long b, c;
    cin >> a >> b >> c;

    int cnt = 0;
    // Tối đa tổng chữ số của số 999,999,999 là 81.
    // Nếu a=1, s có thể lên tới ~10^9/b nhưng s^a phải nhỏ hơn 10^9.
    // Suy ra s <= 10^9.
    // Tuy nhiên, với a >= 1, tổng chữ số S(x) của x < 10^9 là 81.
    // Nhưng 's' là giá trị S(x)^a, nên 's' thực tế là S(x).
    // Không, biến s trong vòng lặp là tổng chữ số S(x).
    // Giới hạn tổng chữ số của số < 10^9 là 81.
    for (int s = 1; s <= 81; ++s) {
        long long val = power(s, a);
        // Kiểm tra tràn số có thể xảy ra nếu s lớn và a lớn, nhưng s <= 81 nên an toàn.
        long long x = b * val + c;

        if (x > 0 && x < 1000000000) {
            if (sumDigits(x) == s) {
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

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

Đây là phiên bản chi tiết hơn của Approach 1. Logic giống hệt nhau: duyệt s từ 1 đến 81. Code ở đây tách biệt hàm tính lũy thừa và chú thích rõ ràng hơn về giới hạn của s. Đây là cách tiếp cận chuẩn và hiệu quả nhất cho bài toán này.

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

Bài học kinh nghiệm

• Tổng chữ số S(x) của số x < 10^9 có giá trị tối đa là 81 (9 chữ số * 9). Đây là chìa khóa để giảm độ phức tạp từ O(N) xuống O(1).
• Thay vì tìm x thỏa mãn phương trình, ta反向 xem xét các giá trị tổng chữ số s có thể có, tính x từ s, rồi kiểm tra tính hợp lệ của x.
• Bài toán có thể được giải quyết bằng cách duyệt qua không gian tìm kiếm rất nhỏ (81 giá trị) thay vì duyệt toàn bộ không gian 10^9.

Lỗi thường gặp

• Quên kiểm tra điều kiện x > 0 và x < 10^9 sau khi tính toán, dẫn đến chấp nhận các nghiệm ngoài phạm vi.
• Lỗi tràn số khi tính s^a nếu sử dụng kiểu int, cần dùng kiểu long long.
• Xác định sai giới hạn trên của vòng lặp duyệt s. Nếu nhầm lẫn giữa s là tổng chữ số và s là giá trị sau khi lũy thừa, có thể chọn sai khoảng giá trị.