SDUT 3068 为了相同的前缀-方程式计算(数学)解题报告

2016-02-02 454 次浏览 解题报告

题面

为了相同的前缀-方程式计算
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;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/02/02/sdut-3068.dream

还不快抢沙发

添加新评论