【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[]; int dd(int a)
{
int d=;
while(a)
{
d+=a%;
a/=;
}
return d;
}
int main()
{
for(int i=; i<; i++)
{
int s=i+dd(i);
if(s>) 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 ;
}

法二

#include<stdio.h>
#include<cstring>
int t,n,ok; int dd(int a)
{
int d=;
while(a)
{
d+=a%;
a/=;
}
return d;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ok=;
for(int i=n-;i<n&&ok;i++)
if(i+dd(i)==n){
printf("%d\n",i);
ok=;
}
if(ok)printf("0\n");
}
return ;
}
上一篇:设置mysql的默认存储引擎


下一篇:实现Fragment的切换和ViewPager自动循环设置切换时间