闲暇时，福尔摩斯和华生玩一个游戏：
在N张卡片上写有N个整数。两人轮流拿走一张卡片。要求下一个人拿的数字一定是前一个人拿的数字的约数或倍数。例如，某次福尔摩斯拿走的卡片上写着数字“6”，则接下来华生可以拿的数字包括：
1，2，3, 6，12，18，24 ....
当轮到某一方拿卡片时，没有满足要求的卡片可选，则该方为输方。
请你利用计算机的优势计算一下，在已知所有卡片上的数字和可选哪些数字的条件下，怎样选择才能保证必胜！
当选多个数字都可以必胜时，输出其中最小的数字。如果无论如何都会输，则输出-1。
Input
输入数据为2行。第一行是若干空格分开的整数（每个整数介于1~100间），表示当前剩余的所有卡片。
第二行也是若干空格分开的整数，表示可以选的数字。当然，第二行的数字必须完全包含在第一行的数字中。
第二行也是若干空格分开的整数，表示可以选的数字。当然，第二行的数字必须完全包含在第一行的数字中。
Output
程序则输出必胜的招法！！
Sample Input
样例输入1
2 3 6
3 6 样例输入2
1 2 2 3 3 4 5
3 4 5
Sample Output
样例输出1
3 样例输出2
4
Source
蓝桥杯
code：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INF 99999999
#define me(a,x) memset(a,x,sizeof(a))
int mon1[]= {,,,,,,,,,,,,};
int mon2[]= {,,,,,,,,,,,,};
int dir[][]= {{,},{,-},{,},{-,}};
int fac[] = {, , , , , , , , , };//i的阶乘
LL getval()
{
LL ret();
char c;
while((c=getchar())==' '||c=='\n'||c=='\r');
ret=c-'';
while((c=getchar())!=' '&&c!='\n'&&c!='\r')
ret=ret*+c-'';
return ret;
}
void out(int a)
{
if(a>)
out(a/);
putchar(a%+'');
}
int kt(int a[],int n)//康托展开
{
int ans=;
for(int i=; i<=n; i++) //下标从1开始
{
int c=;
for(int j=i+; j<=n; j++)
{
if(a[j]<a[i])
c++;
}
ans+=(c*fac[n-i]);
}
return ans+;
} #define max_v 105
int a[max_v];
vector<int> b;
vector<int> vv[max_v]; int dfs(int x)
{
for(int i=vv[x].size()-; i>=; i--)//从大的数开始选，因为大的数约数和倍数少
{
int y=vv[x][i];
if(a[y])//对手选择的数字存在
{
a[y]--;
int flag=dfs(y);//判断对手是否为必胜态
a[y]++;
if(flag)//对手为必胜态，则我为必败态
return ;
}
}
return ;//对手没有必胜态，则我是必胜态
} int main()
{
int x;
me(a,);
string str;
getline(cin,str);
stringstream ss(str);
while(ss>>x) a[x]++;
getline(cin,str);
stringstream st(str);
while(st>>x)
b.push_back(x); sort(b.begin(),b.end());
for(int i=; i<=; i++)
{
if(a[i]!=)
{
for(int j=; j<=; j++)//得到每个i的倍数或者约数
{
if((i%j==||j%i==)&&a[j]!=)
vv[i].push_back(j);
}
}
}
int flag=;
for(int i=; i<b.size(); i++)
{
int x=b[i];//我先手选
if(a[x])//选的数字存在
{
a[x]--;//选了一个
if(dfs(x))//搜索判断我选择该数字是否为必胜态
{
printf("%d\n",x);
flag=;
break;
}
a[x]++;//回退
}
}
if(flag==)
printf("-1\n");
return ;
}