题意

题目链接。

有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，每次操作选择 $k$ 个数，将这 $k$ 个数减去他们的与（二进制运算中的与）的和。求哪些 $k$ 可以在有限次操作内使所有数变成 $0$。

解析

蛮有趣的。把所有数化成二进制后，你考虑每一位。如果共有 $x$ 个数在某一位上为 $1$，那么考虑如果指定了一个 $k$，那么这一位显然每次只能减少 $k$ 个 $1$ 或 $0$ 个 $1$。换言之，如果想要让这一位上全部变为 $0$，需要满足 $k|x$。

发现在这个过程中，每一位是独立的，因为可行的 $k$ 为每一位的 $x$ 的因子，即我们只需要求出每一位上为 $1$ 的数的个数，再将这些个数求一个 $\gcd$，这个求得的 $\gcd$ 的所有因子即为可行的 $k$。

特别的，如果所有数均为 $0$，答案显然可以为 $1\sim n$ 的所有数。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,a[N],t[50];
inline int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
vector<int> ans;
inline void print(int x){//求答案
    ans.clear();
    for(int i=1;i<=sqrt(x);i++){
        if(x%i==0){
            ans.push_back(i);
            if(i*i!=x) ans.push_back(x/i);
        }
    }
    sort(ans.begin(),ans.end());
    for(auto x:ans) printf("%d ",x);
    printf("\n");
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);for(int i=0;i<=30;i++) t[i]=0;
        for(int i=1,x;i<=n;i++){
            scanf("%d",&x);
            for(int j=0;j<=30;j++){
                if(x&(1<<j)) t[j]++;//统计个数
            }
        }
        int g=0;
        for(int j=0;j<=30;j++) g=gcd(g,t[j]);//求 gcd
        if(g==0){for(int i=1;i<=n;i++) printf("%d ",i);printf("\n");}//特判全部为 0
        else print(g);
    }
}