更新时间:2022-08-19 22:35:14
思路; 位运算
分析:
1 题目要求找到k个数,使得这k个数的&的结果能够被2^v整除,并且v的值应该要尽量的大
2 一个数能够被2^v整数,说明这个数的二进制的最右边的1后面刚好是v个0,比如20的二进制为10100,那么刚好可以被2^2整除,那么就有最右边的1的后面0的个数刚好为2个
3 那么我们可以通过从大到小枚举v,然后我们去n个数里面找满足“这个数的二进制的最右边的1后面刚好是v个0”,然后进行求&运算,只要我们找到一个满足的就是最后的ans
代码:
#include<set> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 100010; int n; int num[MAXN]; void solve(){ set<int>s; for(int v = 30 ; v >= 0 ; v--){ int val = 1<<v; int sum; s.clear(); for(int i = 0 ; i < n ; i++){ if(num[i]&val){ if(s.empty()) sum = num[i]; else sum &= num[i]; s.insert(num[i]); } } if(sum%val == 0){ printf("%d\n" , s.size()); set<int>::iterator it = s.begin(); printf("%d" , *it++); for(; it != s.end() ; it++) printf(" %d" , *it); puts(""); return; } } } int main(){ while(scanf("%d" , &n) != EOF){ for(int i = 0 ; i < n ; i++) scanf("%d" , &num[i]); solve(); } return 0; }