3039: 分成互质组（递归）

解题思路:建立数组v记录组别， 遍历每一个数字， 分别和当前组别每一个数字判断是否有大于1的公约数， 如果没有，在v数组中标记该数字的组别， 如果有有， 递归下一个组别， 如果当前组别比 最大组别大， 标记为新组， 返回。

注意事项:

参考代码:

#include<iostream>
using namespace std;
int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
} 
const int N = 1e2 + 10;
int a[N],n,v[N],mx;
void dfs(int l, int pos){
	if(l > mx){
		mx = l;
		v[pos] = l;
		return;
	}
	bool is_group = true;
	for(int i = 0; i < pos; i ++){
		if(v[i] == l && gcd(a[i],a[pos]) > 1) {
			is_group = false;
                        break;
		}
	}
	if(is_group) v[pos] = l;
	else dfs(l + 1, pos);
}
int main()
{
	cin >> n;
	for(int i = 0; i < n; i ++) cin >> a[i];
	for(int i = 1; i < n; i ++){
		dfs(0,i);
	}
	cout << mx + 1 << endl;
	return 0;
}

循环的写法：

#include<iostream>
using namespace std;
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a % b);
} 
const int N = 1e2 + 10;
int a[N],n,v[N];
 
int main()
{
    bool is_group;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    int l = 0;
    for(int i = 1; i < n; i ++){
        is_group = true;
        for(int j = 0; j <= l; j ++){
            for(int k = 0; k < i && v[k] == j; k ++){
                if(gcd(a[i],a[k]) > 1) {
                    is_group = false;
                    break;
                }
            }
            if(is_group) {
                v[i] = j;
                break;
            }
        }
        if(!is_group) {
            v[i] = ++l;
        }
    }
    cout << l + 1;
    return 0;
}