題目大概是這樣:
如果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]);
}
}
如果不妥,還望指出。