分成互质组
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 4518 通过数: 2079
【题目描述】
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
【输入】
第一行是一个正整数n。1 ≤ n ≤ 10。
第二行是n个不大于10000的正整数。
【输出】
一个正整数，即最少需要的组数。
【输入样例】
6
14 20 33 117 143 175
【输出样例】
3
分析
对于第x+1个数，要么把它塞进前面的组里，要么自成一组。
枚举所有已存在的组，如果可以加入，就加入，更新所加入组的元素个数和元素。
递归。。回来
退出这个组，还原这个组的元素个数和元素
判断能否加入下一个组
重复操作
判断完所有已知组
自成一组，组数加一，更新新组元素个数和元素
递归。。
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define F(i,a,b) for(int i=a;i<=b;i++)
#define UF(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N = 15;
int ans = 20, n, a[N], gro[N][N] , tot[N];
int t;
int gcd(int a, int b){//通过找gcd判断互质
if(b==0){
return a;
}
else return gcd(b, a%b);
}
bool huzhi(int a[], int b, int tot){//判断b能否加入a组
if(b == 1) return 1;
for(int i = 1; i <= tot ; i++){
if(gcd(a[i],b) != 1) return 0;
}
return 1;
}
void divi(int x, int zu){//a[x]是当前
//这一堆是用来调试的，可忽略
// if (t == 1) return;
// cout <<"a x+1 zu tot gro"<<endl;
// cout <<a[x + 1]<<" "<<x + 1<<" "<<zu<<" ";
// F(i,1,zu)
// cout << tot[i] <<",";
// cout << " ";
// F(i,1,zu){
// F(j,1,tot[i]){
// cout << gro[i][j] <<",";
// }
// cout <<"..";
// }
// cout << endl ;
if(x == n){
if(zu < ans){
ans = zu;//更新答案
}
//加入了同样的调试
// cout <<"a x+1 zu tot gro"<<endl;
// cout <<a[x]<<" "<<x + 1<<" "<<zu<<" ";
// F(i,1,zu){
// cout << tot[i] <<",";
// }
// cout << " ";
// F(i,1,zu){
// F(j,1,tot[i]){
// cout << gro[i][tot[j]] <<",";
// }
// cout <<"..";
// }
// cout << endl ;
// t = 1;
return;
}
F(i,1,zu){
if(huzhi(gro[i], a[x + 1], tot[i])){//我们是为a[x+1]找归宿
tot[i]++;
gro[i][tot[i]] = a[x + 1];
divi(x + 1, zu);
tot[i]--;
}
}
tot[zu + 1] ++;
gro[zu + 1][1] = a[x + 1];
divi(x + 1, zu + 1);
tot[zu + 1]--;
}
int main()
{
std::cin >> n;
F(i,1,n) std::cin>>a[i];
tot[1] = 1;
gro[1][1] = a[1];
divi(1,1);
cout << ans <<endl;
return 0;
}
/*10
1024 13 169 97 4 5 6 25 30 729
*/