---
# System prepended metadata

title: UVa 1583 - Digit Generator

---

# UVa 1583 - Digit Generator
---
## 題目大意
有多筆詢問，每次要求回答n最小的生成元。也就是指一數和其每一位的總和為n。比方說n為216時要輸出198，因為198+1+9+8=216。

---
## 題解
對於每個n，由於n<=1e5，很容易可以發現最多只要從n-9*6枚舉到n就可以找到最小生成元。但詢問可能有很多筆，這樣做會TLE，所以其實可以事先建表算好每個數字的答案，這樣每筆詢問只要O(1)。

---
```=C++
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF 2147483647
#define ft first
#define sec second
#define pr pair<int,int>
#define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int t ,n ,m ,k ,a ,cnt ,ans[100005];
const int MAXN = 1e9;
inline void find(int x)
{
	int sum=x ,tp=x;
	while(x) sum+=x%10 ,x/=10;
	ans[sum] = min(tp ,ans[sum]);
}
int main() 
{
	fill(ans ,ans+100001 ,MAXN);
	for(int i=1 ;i<=1e5 ;i++) find(i);
	cin>>t;
	while(t--)
	{
		cin>>n;
		if(ans[n]==MAXN) cout<<"0\n";
		else cout<<ans[n]<<'\n';
	}
}
```