「Codeforces」の bitmasks

「Codeforces」の bitmasks

Codeforces Round #751 (Div. 2)
date：2021/11/09

---

题目大意：

规定一种摧毁数组 a [ n ] a[n] a[n]的方式：

1. 选择 k k k 个数 下标为： i 1 , i 2 . . . i k i_1,i_2...i_k i1​,i2​...ik​
2. 求 x = a i 1 & a i 2 & a i 3 . . . & a i k x = a_{i_1} & a_{i_2}&a_{i_3}...&a_{i_k} x=ai1​​&ai2​​&ai3​​...&aik​​
3. 让选到的 k k k 个数减去 x x x；
4. 数组元素均为0时,即:摧毁

输出所有可以取到的 k k k

思路：

参考文章

一个数组被摧毁即是让每一个数的二进制表示中的1变为0；
那么当一个数的第 i i i位由 1 → 0 1rightarrow0 1→0 ,就会使另外 k - 1个数的第 i i i位由 1 → 0 1rightarrow0 1→0；(模拟一下)
那么就可以得知 k k k 为 所有数第 i i i 位 1 1 1 的数量的倍数；
设所有数第 i i i位 1 1 1 的数量为 g i g_i gi​ 那么 k k k 就为 g 1 g 2 . . g n g_1 g_2 .. g_n g1​g2​..gn​ 的最小公倍数的约数;

Code:

// Problem: C. Array Elimination
// Contest: Codeforces - Codeforces Round #751 (Div. 2)
// URL: https://codeforces.com/contest/1602/problem/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
#define _orz ios::sync_with_stdio(false),cin.tie(0)
#define mem(str,num) memset(str,num,sizeof(str))
#define forr(i,a,b) for(int i = a;i <= b;i++)
#define forn(i,n) for(int i = 0; i < n; i++)
#define all(a) (a.begin(),a.end())
#define dbg() cout << "0k!" << endl;
//#define _DEBUG
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6+10;
const ll MOD = 1e9+7;
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
void so1ve(){
	int n; cin >> n;
	vector p(31);
	forr(i,1,n){
		ll x; cin >> x;
		forr(j,0,30) p[j] += (1&(x>>j)); // 查看一个数二进制下第i位的值;
	}
	int g = p[0];
	//forr(i,0,30) cout << p[i] << endl;
	forr(i,1,30) g = gcd(g,p[i]);
	if(g == 0){
		forr(i,1,n) cout << i <<" ";
		return;
	}
	for(int i = 1; i <= g;i++){
		if(g%i == 0) cout << i <<" ";
	}
	cout << endl;
}
int main()
{
#ifdef _DEBUG
    //freopen("input.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int t; cin >> t;
    while(t--) so1ve();
    return 0;
}

场号题目Codeforces Round #731 (Div. 3)D. Co-growing Sequence