分成互质组 为了这题开了张月卡 哈哈哈哈哈 呃

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int f(int b, int c) {
    if (c == 0) {
        // 如果c为0，则返回b
        return b;
    }
    // 递归调用f函数，参数为c和b对c取模的结果
    return f(c, b % c);
}
int main() {
    int n, a;
    cin >> n; // 输入整数n，表示数组的大小
    vector<int> v, kk; // 定义两个整型向量v和kk
    for (int i = 1; i <= n; i++) {
        cin >> a; // 输入数组元素
        v.push_back(a); // 将输入的元素添加到向量v中
    }
    int kkk = 0; // 初始化计数器kkk为0
    bool k; // 定义布尔变量k
    for (int i = 0; i < n; i++) {
        kk.clear(); // 清空向量kk
        if (v[i] == -1) {
            continue; // 如果当前元素为-1，跳过本次循环
        }
        kk.push_back(v[i]); // 将当前元素添加到向量kk中
        for (int j = 0; j < n; j++) {
            if (v[j] == -1) {
                continue; // 如果当前元素为-1，跳过本次循环
            }
            k = true; // 初始化布尔变量k为true
            for (int g = 0; g < kk.size(); g++) {
                if (f(v[j], kk[g]) != 1) {
                    k = false; // 如果v[j]和kk[g]的最大公约数不为1，设置k为false
                }
            }
            if (k) {
                kk.push_back(v[j]); // 如果k为true，将v[j]添加到向量kk中
                v[j] = -1; // 将v[j]设置为-1，表示已处理过
            }
        }
        kkk++; // 增加计数器kkk的值
        v[i] = -1; // 将v[i]设置为-1，表示已处理过
    }
    cout << kkk << endl; // 输出计数器kkk的值
    return 0;
}