题目大意：给出一个数字，找到一个最小的数字，使得这个数字各位数的乘积等于给定的数字。
网上许多人的做法我不晓得如何证明做法是正确的。
由于一个数字的因子个数不会很多，采用DFS即可。
以下是我的代码：
#include<vector>
#include<cstdio>
using namespace std;
int len;
vector<int> ans,now;
bool update()
{
if(len>now.size())
return true;
for(int i=0;i<len;i++)
if(ans[i]>now[i])
return true;
else if(ans[i]<now[i])
return false;
return false;
}
void dfs(int depth,int x,int last)
{
if(x==1)
{
if(update())
{
ans=now;
len=depth-1;
}
return;
}
if(depth>len)
return;
for(int i=last;i<=9;i++)
if(x%i==0)
{
now.push_back(i);
dfs(depth+1,x/i,i);
now.pop_back();
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
if(n==0 || n==1)
{
printf("%d\n",n);
continue;
}
len=0x7f7f7f7f;
now.clear();
dfs(1,n,2);
if(len==0x7f7f7f7f)
printf("%d\n",-1);
else
{
for(int i=0;i<ans.size();i++)
printf("%d",ans[i]);
printf("\n");
}
}
return 0;
}
posted on 2011-05-24 11:04
lee1r 阅读(386)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索 、
题目分类：数学/数论