题面

为了相同的前缀-方程式计算
Time Limit: 1000ms Memory limit: 65536K

题目描述
输入a,b,c,找出所有符合下列方程的x，且x为最少1位，最多9位的正整数；
x = b·s(x)^a + c, （s(x)是指正整数x的各位数之和）。

输入
多组输入，每一组输入为三个整数a,b,c（1 ≤ a ≤ 5; 1 ≤ b ≤ 10000;  - 10000 ≤ c ≤ 10000 ）;

输出
第一行输出符合条件的有多少个x，第二行输出所有符合条件的x（若x为0，则第二行不输出）。

示例输入
3 2 8
1 2 -18

示例输出
3
10 2008 13726
0

提示

来源
ff

解题思路

注意到题目中的 x 的范围是 1-999999999，这么大的范围，直接暴力穷举显然是会超时的。本题主要的难点在于如何将穷举范围控制在我们能接受的范围内。观察题目给出的方程：

$x = b\times s(x)^{a}+c\tag{1}$

不难发现，s(x) 在 x 取得最大值，即 x = 999999999 时相应地取得最大值，即 81。将 s(x) 看作 x 的函数，我们不难得出 s(x) 的定义域为 [1, 999999999]，值域为 [1, 81]。至此，很多读者应该已经想到了，如果我们在 s(x) 的值域内穷举所有情况，即可大大减少运算量。因此，我们将方程两边都看作 s(x) 的自变量，做如下变换：

$x = b\times s(x)^{a}+c\tag{1}$

变换为：

$s(x) = s [ b\times s(x)^{a}+c ]\tag{2}$

这样，由我们得到的与原方程等价的方程 (2)，只需要从 1 到 81 穷举所有情况，如果满足方程左右两边相等，则在数组里记录 $b\times s(x)^{a}+c$ （即 $ x $）的值即可。

这样我们就可以写出本题的代码了：

#include <cstdio>
#define MAX_X 999999999
#define MAX_SX 81
using namespace std;

int s(long long x);
long long p(int x, int a);

int main(int argc, char const *argv[])
{
    int a, b, c, x, cnt;
    long long ans[81], temp;
    while(~ scanf("%d %d %d", &a, &b, &c)){
        cnt = 0;
        //从 1 到 81 穷举所有情况，i 即 s(x)
        for(int i=1; i<=MAX_SX; ++i){
            temp = b*p(i, a)+c;
            //记录满足方程且在规定范围内的 x
            if(i==s(temp) && temp>=1 && temp<=MAX_X)
                ans[cnt++] = temp;
        }
        printf("%d\n", cnt);
        for(int i=0; i<cnt; ++i){
            if(i) printf(" ");
            printf("%lld", ans[i]);
        }
        if(cnt) printf("\n");
    }
    
    return 0;
}

//求每一位数字之和的 s 函数
int s(long long x)
{
    int sum = 0;
    while(x){
        sum += x%10;
        x /= 10;
    }

    return sum;
}

//幂函数
long long p(int x, int a)
{
    long long ans = 1;
    for(int i=0; i<a; ++i){
        ans = ans*x;
    }

    return ans;
}