Uva(Digit Generator，1583) 生成元



题目大概是这样：

如果x加上x的各位数之和等于y，就说x是y的生成元.

给出n(1<=n<=100000),求n的最小生成元,  无解输出0.

 例如 n=216,121,2005 应输出 198 0 1979

当然，拿到题目我第一反应是枚举，确实我使用枚举AC了。。

并不是枚举1-n. x=（n的位数）*9..  枚举(n-x,n)即可

比如 216 只需要枚举（n-3*9,n）..这是显然的。

直接上代码，尽管写的很挫。

#include"cstdio"
#include"cstdlib"
#include"cstring"
#include"algorithm"
#include"iostream"
using namespace std;
int data[10];
int main()
{
	int n;
	int times;
	scanf("%d",×);
	for(int k=0;k<times;k++)
	{
		scanf("%d",&n);
		int cnt=0;  //统计多少位 
		int tem=n;
		while(tem)
		{
			cnt++;
			tem/=10;
		}
		int ok=0;
		for(int i=n-cnt*9;i<=n;i++)
		{
			int sum=i;
			tem=i;
			while(tem)
			{
				sum+=tem%10;
				tem/=10;
			}
			if(sum==n)
			{
				ok=1;
				printf("%d\n",i);
				break; 
			}
		}
		if(!ok)  printf("0\n");  //无解 		
	}
	return 0;
}
           

离线做法： 高效率

#include"cstdio"
#include"cstring"
const int maxn=100000+5;
int ans[maxn];  
void solve()  //离线做法 
{
    memset(ans,0,sizeof(ans));
	for(int i=1;i<maxn;i++)
	{
	    int x=i,y=i;
		while(x){y+=x%10;x/=10;}
		if(ans[y]==0||i<ans[y])  ans[y]=i;
	} 
}
int main()
{
	int T,n;
	solve();
    scanf("%d",&T);
    while(T--)
    {
    	scanf("%d",&n);
    	printf("%d\n",ans[n]);
	}
}
           

如果不妥，还望指出。