题目链接https://cometoj.com/contest/42/problem/B

粘贴过来有些错误，将就看吧

题目描述

在大木博士那里，小智发现推荐的三只宝可梦都已经被別人選走了，最终他挑选了皮卡丘作为自己的第一只宝可梦。皮卡丘不是很待见小智，但还是在危急之时救了小智一命，小智和皮卡丘的关系也因此熟络了许多。皮卡丘因为救小智受了重伤，小智急忙带着皮卡丘去常磐市的医院治疗。

常磐市经常发生绑架宝可梦的事件，犯人是一男一女，他们这天也来到了常磐市的治疗中心，准备劫走治疗中心里面罕见的宝可梦。用"华丽"的方式登场后，将他们的宝可梦瓦斯弹和阿柏蛇放出来，开始攻击和搜寻每一间房间，并且把电源给切断了。

小智、小霞和护士姐姐迅速把趟在病床上的皮卡丘推进传送室，停电后，护士姐姐说他们有备用电源，小智放眼一看，正在发电的居然是一群训练有素的皮卡丘！小智发现，每一个皮卡丘后背都有一个数字，护士姐姐解释说:"皮卡丘集中发电的能力跟他们后背的数字有关，当上场发电的皮卡丘们后背的数字任两个数字都互质的话，他们的发电能力就会强大无比！当然，同样都是互质的情况下，上场的皮卡丘数量越多越好。"

不管是战斗，还是发电，我们都需要皮卡丘！现在，已知共有 nn 只皮卡丘，给出每只皮卡丘后背的数字，请你选择尽量多的皮卡丘上场，使得它们后背的数满足任意两个数字互质。只需输出你最多能选择了多少只皮卡丘。

注：两个数字互质当且仅当他们没有 11 以外的正公因数。

输入描述

输入有多组数据，第一行输入一个正整数 TT (T \le 10T≤10) ，表示测试组数。

然后对于每组数据，

第一行有一个正整数 nn (n \le 14n≤14)，第二行有 nn 个两两相异的数 a_1,a_2,\ldots,a_na1​,a2​,…,an​ (1 \le a_i \le 10^91≤ai​≤109)，代表这 nn 只皮卡丘后背的数字。

输出描述

对于每组数据，输出一个正整数表示最多可以选几只皮卡丘，使得任两只皮卡丘后背的数字都互质。

样例输入 1 

2
3
3 4 5
7
7 6 5 4 3 2 1

样例输出 1

3
5

提示

对于样例中第一组数据，可以三只皮卡丘同时上场，因为他们后背上的数字两两互质。

对于样例中第二组数据，我们可以选后背号码分别为 7,5,3,2,1 的 5 只皮卡丘。

状压枚举+暴力判断

（__gcd好像比gcd快）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
//int gcd(int a,int b){
//	return b?gcd(b,a%b):a;
//}
int a[20];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
	    int n;
	    scanf("%d",&n);
	    for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
		int ans=0;
	    for(int i=1;i<=(1<<n)-1;i++){
	    	vector<int> v;
	    	int cnt=0;
	    	for(int j=0;j<n;j++){
	    		if(i&(1<<j)) {
	    			v.push_back(a[j+1]);
	    			cnt++;
				}
			}
			if(cnt<ans) continue;
			bool flag=true;
			for(int j=0;j<v.size();j++){
				for(int k=j+1;k<v.size();k++){
					if(__gcd(v[j],v[k])!=1) {
						flag=false;
						break;
					}
				}
				if(!flag) break;
			}
			if(flag) ans=max(ans,cnt);
		}
	    printf("%d\n",ans);
	} 
	return 0;
}