UVA 1583 Digit Generator

Posted by

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;
}
  ]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注