UVa1583 Digit Generator 生成元 題解

UVa1583 Digit Generator 生成元

題目連結：UVa1583

題目描述

輸入格式

輸出格式

題目翻譯

如果x加上x的各個數字之和得到y，也就是說x是y的生成元。給出n(1<=n<=100000)，求最小生成元。無解則輸出0。

輸入輸出樣例

輸入

3
216
121
2005
           

輸出

198
0
1979
           

題目分析

假設所求生成元為m，不難得出m<n，是以可直接枚舉所有小于n的m，看看哪些m是n的生成元。但這樣做效率過低，因為對于每個n都需要枚舉n-1個數。是以我們可以提前枚舉1至100000内所有m，計算出其所對應的值，對于每個n則隻需查表即可。

Code

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100010;
int ans[maxn];
int main()
{
	int t,n;
	memset(ans,0,sizeof(ans));
	for(int m=1;m<maxn;m++)
	{
		int x=m,y=m;
		while(x>0)
		{
			y+=x%10;
			x/=10;
		}
		if(ans[y]==0 || m<ans[y]) ans[y]=m;
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		printf("%d\n",ans[n]);
	}
	return 0;
} 
           

以上就是《UVa1583 Digit Generator 生成元》的詳細題解，如果您認為我的文章對您起到了幫助作用，懇請點贊關注支援一下，您的鼓勵就是我前進的最大動力。

我是Horseman：一名正在成長的蒟蒻OIer，UVa題解系列持續更新中，感謝大家的鼓勵支援。