[搜索] 质数

题目描述

给定 $n$ 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
在满足最少的组数的情况下，使得元素个数最多的那一组的元素个数尽可能的少。

输入格式

第一行 $1$ 个数 $n$。
接下来 $n$ 行，每行 $1$ 个数字表示 $a_i$。

输出格式

一行两个正整数，第一个数是最少的组数，第二个数是满足最少组数的境况下，元素个数最多的那一组的元素个数。

样例

样例输入1：

6
14 
20 
33 
117 
143 
175

样例输出1：

3 2

样例输入2：

4
2 
4 
7 
9

样例输出2：

2 2

数据范围

对于 $30\%$ 的数据，$n\le 8$。
对于 $60\%$ 的数据，$n\le 10$。
对于 $100\%$ 的数据，$n\le 15,1\le a_i\le 10^4$。

题解

由于 $n$ 的范围很小，所以可以直接爆搜。
dfs(int x, vector<int> v, int l1, int l2)，$x$ 表示当前搜到的数的编号，$v$ 表示当前的情况，$l1$ 表示 $ans1$，$l2$ 表示 $ans2$。
如果 $x>n$，说明已经搜完了，更新答案。
否则继续搜索，接下来有两个情况：

• 重新开一个新的组。
• 在现在的组中，找到一个组使得每个数都与其互质，放进去。

接下来进行剪枝：

1. 如果当前的已经比答案差了，直接返回。
2. 还可以进行记忆化，如果搜到第 $i$ 个数的答案已经不比前面搜到的更优，返回。

代码：

int a[20];
bool check(int x, int y){//判断互质
	如果 gcd(x, y) 是 1，则互质返回1，否则返回0
}
//组数，每组中最大元素个数
int ans1 = 1e9, ans2 = 1e9;
void dfs(int x, vector<int> v[20], int l1, int l2){
	if(l1 > ans1){
		return;
	}
	if(l1 == ans1 && l2 >= ans2){
		return;
	} 
	if(x > n){
		if(l1 < ans1){
			ans1 = l1;
			ans2 = l2;
		}
		else if(l1 == ans1){
			ans2 = min(ans2, l2); 
		}
		return;
	}
	vector<int> t[20];
	for(int i = 1; i <= l1; ++ i){
		for(auto j : v[i]){
			t[i].push_back(j);
		}
	}
	----新开一组----
	t[l1 + 1].push_back(a[x]);
	dfs(x + 1, t, l1 + 1, max(l2, 1));
	----从已有的组中选出组放进去----
	for(int i = 1; i <= l1; ++ i){
		int len = 0, fl = 1;
		for(auto j : v[i]){
			++ len;
			if(check(j, a[x]) == 0){
				fl = 0;
				break;
			}
		}
		//互质
		if(fl){
			vector<int> t1[20];
			for(int i1 = 1; i1 <= l1; ++ i1){
				for(auto j1 : v[i1]){
					t1[i1].push_back(j1);
				}
			}
			t1[i].push_back(a[x]);
			dfs(x + 1, t1, l1, max(l2, len + 1));
		}
	}
}
int main(){
	输入
	vector<int> v[20];
	dfs(1, v, 0, 0);
	输出
}