Codeforces Round #751 (Div. 2)-C. Array Elimination

문제 설명

음이 아닌 정수로 이루어진 배열 $a_1,a_2,...,a_n$ 이 주어진다.

정수 $k(1\le k\le n)$ 에 대해서 제거라는 연산을 다음과 같이 정의하자.

• 서로 다른 배열의 인덱스 $(1\le i_1<i_2<...<i_k\le n)$ $k$개를 선택한다.
• $x=a_{i_1}\wedge a_{i_2}\wedge ...\wedge a_{i_k}$ 를 계산한다.
• 각 $a_{i_1},a_{i_2},...,a_{i_k}$ 에 $x$를 뺀다. 그리고 나머지 원소들은 그대로 둔다.

배열 $a$에 있는 모든 원소의 값을 $k$를 매개변수로 하는 제거 연산을 유한번 반복해서 $0$ 이 되게 만들 수 있는 모든 $k$값을 구하는 것이 목적이다. 어떤 배열 $a$라도 $k$ 값이 반드시 1개는 있다.

먼저 $k$를 선택하고 선택한 $k$값에 대한 연산만 이후에 계속 해야한다는 점을 잊지말자.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t(1\le t\le {10}^4)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 배열 $a$의 길이 $n(1\le n\le 200000)$ 이 주어진다.

각 테스트케이스의 두번째 줄에는 배열 $a$의 초기값인 $n$개의 정수 $a_1,a_2,...,a_n(0\le a_i<2^{30})$ 이 주어진다.

Output
각 테스트케이스마다 가능한 모든 $k$값을 공백을 기준으로 출력한다.

Example
input
5
4
4 4 4 4
4
13 7 25 19
6
3 5 3 1 7 1
1
1
5
0 0 0 0 0

output
1 2 4
1 2
1
1
1 2 3 4 5

문제 접근

사용한 알고리즘: 비트마스크, 정수론, 수학
걸린 시간 : 00:06
virtual contest에서 2번 문제에 시간을 많이 쓰지 않았다면 실전에서 풀 수 있을 것 같은 자신감을 가진 문제이다. 실제로 대회가 끝나고 30분정도 시간을 써서 문제를 풀어봤는데 문제에서 요구하는 정해에 완전 근접한 방법에 도달했다. 이렇게 내가 발전하는 것일까? 진짜진짜 rating 1200대의 벽을 뚫고 싶다. 진짜.

일단 문제 조건에 $a_i$값이 $2^{30}$ 보다 작다는 것과 $\wedge$ 연산을 다루는 것을 보자마자 비트마스크 문제라는 것을 알고 시작했다. 처음 문제를 접근할때 예시에 나와있는 숫자들을 이진수로 모두 적어봤다. 그러자 and연산의 성질과 더불어 어떻게 푸는지 길이 보였는데, and연산은 두 수가 비트가 1일때만 1을 나타내기 때문에 1의 개수를 세는 것이 이 문제의 키포인트라는 것을 알았다.

배열 $13,7,25,19$ 일때를 보자. 각각을 이진수로 나타내보면

• 01101
• 00111
• 11001
• 10011

이고, 만약 25와 19를 선택하면 다음과 같이 된다.

• 01101
• 00111
• 01000
• 00010

25와 19에서 같은 자리에 1이 모두 있는 경우 그 1만 사라지는 것을 볼 수 있다. 즉 원소를 $k$개 선택하면 같은 줄에 있는 1이 $k$개 사라지게 되고, 이 연산을 계속 반복해서 모두 0이 되게 만들면 된다. 이러면 어느 정도 감이 올 것이다.

같은 줄에 있는 1의 개수만큼 $k$를 선택할 수 있고, $k$의 약수는 반드시 같은 줄에 있는 모든 1을 지울 수 있다. 예를 들어 1이 4개 있다면 $k=4$ 인경우 4개의 수를 선택해서 모든 1을 지울 수 있다. 그리고 4의 약수인 2를 선택하면 2번의 연산으로 $1$ 4개를 다 지울 수 있다. 마지막으로 4의 약수인 1을 선택하면 당연히 지울 수 있다.

이 $k$는 모든 둘에 공통되어야 하고, 최대값을 가져야 한다. 최대의 공통 된수? 어떤 수가 떠오를까? 바로 최대공약수이다. 즉 모든줄에 대해서 1의 개수를 구한다음 그 수의 최대공약수를 구하고, 그 값의 약수들을 출력하면 문제를 풀 수 있다.

혹은 $k$값은 $(1\le k\le n)$ 이므로 $1$부터 $n$까지 모든 경우를 세서, 나누어 떨어지지 않는다면 출력하지 않고 모든 줄에 있는 1의 개수 값에 대해 다 나누어 떨어지면 출력하는 방식으로도 문제를 풀 수 있다. 이 방법이 가능한 이유는 이 수의 최대 자릿수는 $2^{30}$인 $30$자리이고, $n$의 최대값은 $200000$이므로 최대 $6\cdot {10}^6$ 번 연산을 하게되고, 이 연산은 충분히 시간제한 안에 들어온다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[n];
        for(int i = 0; i < n; i++) cin >> arr[i];

        int cnt[31] = {};
        for(int i = 0; i <= 30; i++){
            for(int j = 0; j < n; j++) cnt[i] += (arr[j] & (1 << i) ? 1 : 0);
        }

        for(int i = 1; i <= n; i++){
            bool flag = true;
            for(int j = 0; j <= 30; j++){
                if(cnt[j] % i != 0) flag = false;
            }
            if(flag) cout << i << " ";
        }
        cout << "\n";
    }
    return 0;
}