An Easy Number Game（生成序列）

D - An Easy Number Game

Crawling in process... Crawling failed Time Limit:2000MS     Memory Limit:65535KB     64bit IO Format:%lld & %llu

Submit Status

Description

There are 8 non-negative intergers (no greater than 9) and a number x, can you make a eight-digit number(without leading zeros) with these intergers with the additional condition that the eight-digit number should be divided by the number x.

Input

The first line of the input contains a single integer T (1 <= T <= 100), the number of test cases, followed by the input data for each test case. The first line of each test case contains 8 integers, while the second line contains the interger x (1 <= x <= 100000000).

Output

For each case, if you can form such a eight-digit number,output "Yes", otherwise,output "No".

Sample Input

2
1 2 3 4 5 6 7 8
12345678
1 2 3 4 5 6 7 8
12345677

Sample Output

Yes
No 

       题意：

       有T个例子，8个少于9的非负数组成的数，输入这8个数，判断有一个组成数能否被x整除，如果能，则输出Yes，不能则输出No。

 

       思路：

       用next_permutation()函数来不断生成排列数，生成一个就组成一个新的数判断能否被x整除，一旦有则输出Yes，无则输出No。（注意：因为输入的8个数之中可以存在非负数，即有可能是0，则应排除前导0的情况）

       AC：

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	int number[10],temp;
	int i,n;
	long long x,t;
	scanf("%d",&n);
	while(n--)
	{
	 	temp=0;
	 	for(i=0;i<8;i++)
	   		scanf("%d",&number[i]);
	 	scanf("%lld",&x);
	 	sort(number,number+8);
	    do
	    {
			t=0;
			i=8;
			if(!number[i-1]) continue;
			while(i--)
			{
			  t=t*10+number[i];
			}
//从后往前扫，判断最后一位（最高位为最后一位）
			if(t%x==0) 
			{
				temp=1;
				break;
			}
	    }while(next_permutation(number,number+8));
	if(temp) printf("Yes\n");
	else     printf("No\n");
    }
	return 0;
}

   总结：

   1.要忽略前导0的情况，因为输入的数可能是0，那么排列的时候第一位有可能是0；

   2.第一位为0的数量和最后一位为0的排列数量是一样的，但是这题不是单纯看数目，关键是要看这个数能否整除x，就算数量能抵消，本身排出来的这个数也是不一样的，所以影响结果的关键是本身的这个数，而不是符合条件总共的数量。所以要不从头往后扫，然后判断第一位（最高位为第一位）；要不从后往前扫，判断最后一位（最高位为最后一位）。