UVA 1583 Digit Generator
摘要：
題目連結：https://www.luogu.org/problemnew/show/UVA1583
思路：
看到這道題就想著打表。然後打出來了提示程式碼過長。。。
採用$n^2$列舉方式，T了。。。反過頭來想，用另一種列舉方式會大大提升效率。
設$x$為$y$...
題目連結：https://www.luogu.org/problemnew/show/UVA1583
思路：
看到這道題就想著打表。然後打出來了提示程式碼過長。。。
採用$n^2$列舉方式，T了。。。反過頭來想，用另一種列舉方式會大大提升效率。
設$x$為$y$的生成元，則$x<y$。
之前的列舉方式是列舉$y$，現在倒過來即可。
只需要判斷2種情況即可。
程式碼：
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
static const int MAXN=100000;
using namespace std;
int n,y,x,num,m,ans[MAXN+5];
inline int read(){
int x=0;bool sign=false;
char alpha=0;
while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
return sign?-x:x;
}
inline void make(){
for(int i=1;i<=MAXN;i++){
y=num=i;
while(y){
m=y%10;
num+=m;
y/=10;
}
if(!ans[num]||i<ans[num]) ans[num]=i;
}
}
int main(){
make();
n=read();
for(int i=1;i<=n;i++){
x=read();
printf("%d\n",ans[x]);
}
return 0;
}