Tìm số nghiệm của phương trình X = B*Sm(X)^A + C bằng C++

Mô tả bài toán

Cho A,B,C. Đếm số X ∈ [1, 10⁹] thỏa X = B × (tổng chữ số của X)^A + C.

Ví dụ

A=3, B=6, C=4 → Output: 3.

Giải thuật

Tổng chữ số tối đa của X ≤ 10⁹ là 81 (9×9). Duyệt digSum từ 1 đến 81, tính X = B×digSum^A+C. Nếu X < 10⁹ và tổng chữ số của X bằng digSum → đếm nghiệm.

Mã nguồn C++

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

int countSolutions(int a, int b, int c) {
    int cnt = 0;
    for (int digSum=1; digSum<=81; digSum++) {
        long long sol = 1LL*b*pow(digSum,a) + c;
        if (sol >= 1e9) continue;
        int sum=0, tmp=sol;
        while (tmp) { sum += tmp%10; tmp/=10; }
        if (sum == digSum) cnt++;
    }
    return cnt;
}

int main() {
    int a=3,b=6,c=4;
    cout << "Number of solutions: " << countSolutions(a,b,c);
    return 0;
}

Đầu ra

The number of solutions of the equations is 3