关于二进制的题
程序员文章站
2022-05-08 22:54:40
...
#include<cstdio>
#include<algorithm>
using namespace std;
/// 要使⽤用 __gcd 必须 include algorithm using namespace std;
int __gcd(int a,int b)
{
return b?__gcd(b,a%b):a;
}
const int MAX_N = 14;
int a[MAX_N];
/// 此函式能获得 x 从最低位数来第 i 位的数字(位数从 0 开始编号)
int get_bit(int x, int i) {return (x >> i) & 1;}
///检查 x 对应到的⼦子集是否满⾜足任两数都互质
bool coprime_in_subset(int n, int x){
for(int j = 0; j < n; j++) {
for(int k = 0; k < j; k++) {
if(get_bit(x, j) && get_bit(x, k)) {
if(__gcd(a[j], a[k]) != 1) return false;
} }
}
return true;
}
void solve_one_test() {
int n;
int an = 0;
scanf("%d", &n);
for(int i = 0;i < n;i++) scanf("%d", &a[i]);
for(int i = 0;i < (1<<n); i++){
if(coprime_in_subset(n,i)){
int cnt = 0;
for(int j = 0;j < n; j++){
cnt += get_bit(i,j);
}
if(an < cnt) an = cnt;
}
}
printf("%d\n",an);
}
int main()
{
int t;
while(scanf("%d",&t)!=-1)
{
while(t--)
{
solve_one_test();
}
}
}
上一篇: 蓝桥杯: 明码