欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关于二进制的题

程序员文章站 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();
        }
    }
}

添加链接描述
添加链接描述

相关标签: 二进制