Coderforces 1601A. Array Elimination

链接: http://codeforces.com/problemset/problem/1601/A

题意

给定一个数组，要求你求出所有的k满足：

1. 从数组中选出k个数，并求出他们与运算后的结果x，将这个k个数减去x
2. 重复上述操作直到数组中所有的数都变成0

   解法

   使用位运算计算每一个二进制位上的和。通过计算可以发现，如果所有位的数量能够整除k，则一定可以找到对应的k满足题目中的条件。
   (或可理解为k能整除所有位的数量的最大公约数)

代码

//
//  C.cpp
//  pureCode
//
//  Created by Qjchen on 2021/11/5.
//

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int cas; cin >> cas;
    while(cas--) {
        int n; cin >> n;
        vector<int> bits(32);
        for (int i = 0; i < n; i++) {
            int t; cin >> t;
            for (int j = 0; j < 32; j++) {
                bits[j] += (t >> j) & 1;
            }
        }
        for (int k = 1; k <= n; k++) {
            int flag = 0;
            for (int i = 0 ; i < 32; i++) {
                if (bits[i] % k) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
                cout << k << ' ';
            }
        }
        cout << endl;
    }
    return 0;    
}