1355: 排列组合

题目描述

PIPI现在有一个正整数num , PIPI想把num中的数位进行排列组合得到一个新数(该新数不能等于num),PIPI想知道这个新数是否可能是原数的倍数。
例: 123 重排之后能够得到 132 213 231 312 321

输入

输入第一行包括一个正整数T（T<=100）,代表测试样例组数。
接下来每一行输入一个正整数num (1<=num<=1e9)

输出

对于每个数字num，如果重排之后有可能变成自己的倍数，从小到大输出所有的倍数(换行输出, 指每两个数之间有个换行)。否则输出"Impossible"。

样例输入

2
15
1035

样例输出

Impossible
3105

#include
using namespace std;
const int N=15;
bool vis[N];
int ans[N];
int str[N];
int n,k,num,flag;
vector<int>vt;
unordered_map<int,bool>mp;
void dfs(int now)
{if(now==k){int sum=0;for(int i=0; i<k; i++)sum=sum*10+ans[i];if(mp.count(sum)) return;mp[sum]=1;if(sum%num==0&&sum!=num){flag=1;printf("%d\n",sum);return;}}for(int i=0; i<k; i++){if(!vis[i]){vis[i]=1;ans[now]=str[i];dfs(now+1);vis[i]=0;}}
}
int main()
{memset(vis,0,sizeof(vis));scanf("%d",&n);while(n--){mp.clear(); ///别忘记mp.clear啊啊啊啊flag=0;scanf("%d",&num);int value=num;k=0;while(value){str[k++]=value%10;value=value/10;}sort(str,str+k);dfs(0);if(flag==0)printf("Impossible\n");}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！