題目大意：給出一個數(shù)字，找到一個最小的數(shù)字，使得這個數(shù)字各位數(shù)的乘積等于給定的數(shù)字。
網(wǎng)上許多人的做法我不曉得如何證明做法是正確的。
由于一個數(shù)字的因子個數(shù)不會很多，采用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 閱讀(450)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索 、
題目分類：數(shù)學/數(shù)論