网易 数位重排 模拟

题目描述

牛牛有一个正整数x,牛牛需要把数字x中的数位进行重排得到一个新数(不同于x的数),牛牛想知道这个新数是否可能是原x的倍数。请你来帮他解决这个问题。

输入描述:

输入包括t+1行,第一行包括一个整数t(1 ≤ t ≤ 10),
接下来t行,每行一个整数x(1 ≤ x ≤ 10^6)

输出描述:

对于每个x,如果可能重排之后变为自己的倍数输出"Possible", 否则输出"Impossible".

示例1

输入

2
14
1035

输出

Impossible
Possible

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
bool judge(int num1,int num2)
{
    int vis1[10];
    int vis2[10];
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
    while(num1)
    {
        int t=num1%10;
        vis1[t]++;
        num1/=10;
    }
    while(num2)
    {
        int t=num2%10;
        vis2[t]++;
        num2/=10;
    }
    for(int i=0;i<=9;++i)
    {
        if(vis1[i]!=vis2[i])
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int t,num1;
    cin>>t;
    while(t--)
    {
        cin>>num1;
        int flag=0;
        for(int i=2;i<=9;++i)
        {
            int num2=num1*i;
            //cout<<num1<<" "<<num2<<endl;
            if(judge(num1,num2))
            {
                flag=1;
                break;
            }
        }
        if(flag)
        {
            cout<<"Possible"<<endl;
        }else 
        {
            cout<<"Impossible"<<endl;
        }
    }
    return 0;
}