问题 H: 最小的x
时间限制: 1 Sec 内存限制: 128 MB
提交: 5603 解决: 2781
[状态] [提交] [命题人:cyh]
题目描述
TSQ对DK进行地狱式训练,找出满足下面公式的最小的x (0<x<1,000,000,000)

a,b,c,d 为已知的4个正整数。
s(x) 为x的各个位上的数字之和。
数学是DK的弱项,所以请你来帮忙解决这个问题。
输入
输入包含多组数据
每组数据包含四个数a,b,c,d (1≤a,b,c,d≤100)
输出
对于每组数据,输出x
如果没有符合条件的x,则输出no
每组数据占一行。
样例输入 Copy
10 4 9 4
1 1 1 1
1 2 3 4
样例输出 Copy
24000
1048576
no
提示
样例1:
a=10,b=4,c=9,d=4
最小x=24000;则有s(x)=2+4+0+0+0=6, 满足24000=(6+10)(6+4)(6+9)*(6+4) , 所以答案为24000

这一题看起来好像根本没法做，其实是没法从正面做 。我们发现如果给出abcd让我们去找一个最小的x很难，但是如果给一个x让我们判断是否符合等式就很简单 所以理论上可以枚举所有可能的解 但是x的范围太大了 时间会超限
怎么办？发现s（x）貌似很小 ，即使x到了10的9次方-1 s（x）也只是81 于是思路就来了：枚举s（x）验证x
代码：

#include <bitsdc++.h>
using namespace std;
#define N 1000000005
//x在0到10的9次方之间 s（x）在0到81之间
//对每个s(x)求出对应的x看是否满足条件 要求最小则每次求出来一个更新答案
int main()
{
    int t,x,a,b,c,d,t1;
    int ans;
    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
    {
        ans=N;//对于每组数据要初始化
        for(t=0;t<82;t++)
        {
            x=(t+a)*(t+b)*(t+c)*(t+d);t1=0;
            while(x)
            {
                t1+=x%10;
                x/=10;
            }
            if(t1==t)ans=min(ans,(t+a)*(t+b)*(t+c)*(t+d));//满足条件就更新答案
        }
        if(ans<N)cout<<ans<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}