像素

用户名：dotcpp0735122

访问量：807

签　名：

落山

等　　级
排　　名	6642
经　　验	1395
参赛次数	0
文章发表	15
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

寻找配对数量总和
浏览：3

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

互质？公因数！

　　作者: 像素　　　　发表时间：2024-04-25 11:44:49 浏览：81　|　评论：0　

原题链接：分成互质组

```cpp
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

const int N=20;

vector<int> g[N]; //g[0~i]表示分成了几组,每组的数都互为质数 
int n,a[N],ans=0x3f3f3f3f; //默认解决方案最大 
int g_size; //每当开辟新的组时加1

int gcd(int a,int b){ //互质其实就是求它们的最大公因数 
	return !b ? a : gcd(b,a%b);
}

bool check(int x,int g_i){
    for(int i=0;i<g[g_i].size();i++){
        int f=gcd(x,g[g_i][i]);
		
		if(f>1 && f<=min(x,g[g_i][i])){
			return false;
		}
    }
    
    return true;
}

void dfs(int a_index){
    
    if(g_size>=ans){ //当组的数量大于等于ans的话，那肯定不用再递归了 
    	return ;
	}
    
    if(a_index==n){
    	ans=g_size;
    	return ;
	}
    
    for(int i=0;i<g_size;i++){ //一开始时，肯定一组没有
		if(check(a[a_index],i)){ //将第i组中的所有数字与a[a_index]进行判断是否为互质数 
			g[i].push_back(a[a_index]);
			dfs(a_index+1);
			g[i].pop_back();
		}
	}
	
	g[g_size++].push_back(a[a_index]); //当前数组的值与其它g中的数都不互质开辟新的空间单独放入
	dfs(a_index+1);
	g[--g_size].pop_back(); 
}

signed main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i=0;i<n;i++){
	    cin>>a[i];
	}
	
	dfs(0); //默认从下标0 数组大小一开始为空
	
	cout<<ans<<endl;
	
	return 0;
} 
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

像素

TA的其他文章

你可能喜欢

C二级辅导-温度转换（C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

互质？公因数！

评论区

精彩推荐

整除问题（C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

矩阵转置（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

震宇大神的杀毒软件（C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

像素

TA的其他文章

你可能喜欢

C二级辅导-温度转换 （C++代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

互质？公因数！

评论区

精彩推荐

整除问题 （C语言代码）

逆反的01串 （C++代码）（依旧推荐switch）

C语言程序设计教程（第三版）课后习题10.7 （C++代码）（都说了scanf和gets一般不要混着用）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

矩阵转置 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

震宇大神的杀毒软件 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C二级辅导-温度转换（C++代码）

　　评论区

整除问题（C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

矩阵转置（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

震宇大神的杀毒软件（C++代码）