【UVA 1583】Digit Generator
题意
a加上 a的各位数=b，则b是a的digitSum，a是b的generator，现在给你digitSum，让你求它的最小的generator。
分析
一种方法是：
预处理打表，也就是把1到100000的digitSum求出来，对每个digitSum保存最小的generator。
另一种方法是：
对digitSum-45到digitSum-1的数求它的digitSum，最先算到给定的digitSum的就是最小的generator。
因为最多6位数，每位上的数最大是9，最多5个9，所以a的各位数之和最大是45，b比a最多多45。
代码
法一（打表运行速度更快）
#include<stdio.h>
#include<cstring>
int t,n,ds[100005];
int dd(int a)
{
int d=0;
while(a)
{
d+=a%10;
a/=10;
}
return d;
}
int main()
{
for(int i=1; i<100000; i++)
{
int s=i+dd(i);
if(s>100000) continue;
if(!ds[s]) ds[s]=i;
}
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(ds[n]) printf("%d\n",ds[n]);
else printf("0\n");
}
return 0;
}法二
#include<stdio.h>
#include<cstring>
int t,n,ok;
int dd(int a)
{
int d=0;
while(a)
{
d+=a%10;
a/=10;
}
return d;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ok=1;
for(int i=n-45;i<n&&ok;i++)
if(i+dd(i)==n){
printf("%d\n",i);
ok=0;
}
if(ok)printf("0\n");
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2016-02-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
