Array Elimination (Codeforces 1601A)
Tags: Math, bitmasks

You are given array $$$a_1, a_2, \ldots, a_n$$$, consisting of non-negative integers.Let's define operation of "elimination" with integer parameter $$$k$$$ ($$$1 \leq k \leq n$$$) as follows:  Choose $$$k$$$ distinct array indices $$$1 \leq i_1 < i_2 < \ldots < i_k \le n$$$.  Calculate $$$x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ \ldots ~ \& ~ a_{i_k}$$$, where $$$\&$$$ denotes the bitwise AND operation (notes section contains formal definition).  Subtract $$$x$$$ from each of $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$; all other elements remain untouched. Find all possible values of $$$k$$$, such that it's possible to make all elements of array $$$a$$$ equal to $$$0$$$ using a finite number of elimination operations with parameter $$$k$$$. It can be proven that exists at least one possible $$$k$$$ for any array $$$a$$$.Note that you firstly choose $$$k$$$ and only after that perform elimination operations with value $$$k$$$ you've chosen initially.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{30}$$$) — array $$$a$$$ itself.It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$200\,000$$$.

Output: For each test case, print all values $$$k$$$, such that it's possible to make all elements of $$$a$$$ equal to $$$0$$$ in a finite number of elimination operations with the given parameter $$$k$$$.Print them in increasing order.

Note: In the first test case:  If $$$k = 1$$$, we can make four elimination operations with sets of indices $$$\{1\}$$$, $$$\{2\}$$$, $$$\{3\}$$$, $$$\{4\}$$$. Since $$$\&$$$ of one element is equal to the element itself, then for each operation $$$x = a_i$$$, so $$$a_i - x = a_i - a_i = 0$$$.  If $$$k = 2$$$, we can make two elimination operations with, for example, sets of indices $$$\{1, 3\}$$$ and $$$\{2, 4\}$$$: $$$x = a_1 ~ \& ~ a_3$$$ $$$=$$$ $$$a_2 ~ \& ~ a_4$$$ $$$=$$$ $$$4 ~ \& ~ 4 = 4$$$. For both operations $$$x = 4$$$, so after the first operation $$$a_1 - x = 0$$$ and $$$a_3 - x = 0$$$, and after the second operation — $$$a_2 - x = 0$$$ and $$$a_4 - x = 0$$$.  If $$$k = 3$$$, it's impossible to make all $$$a_i$$$ equal to $$$0$$$. After performing the first operation, we'll get three elements equal to $$$0$$$ and one equal to $$$4$$$. After that, all elimination operations won't change anything, since at least one chosen element will always be equal to $$$0$$$.  If $$$k = 4$$$, we can make one operation with set $$$\{1, 2, 3, 4\}$$$, because $$$x = a_1 ~ \& ~ a_2 ~ \& ~ a_3 ~ \& ~ a_4$$$ $$$= 4$$$. In the second test case, if $$$k = 2$$$ then we can make the following elimination operations:  Operation with indices $$$\{1, 3\}$$$: $$$x = a_1 ~ \& ~ a_3$$$ $$$=$$$ $$$13 ~ \& ~ 25 = 9$$$. $$$a_1 - x = 13 - 9 = 4$$$ and $$$a_3 - x = 25 - 9 = 16$$$. Array $$$a$$$ will become equal to $$$[4, 7, 16, 19]$$$.  Operation with indices $$$\{3, 4\}$$$: $$$x = a_3 ~ \& ~ a_4$$$ $$$=$$$ $$$16 ~ \& ~ 19 = 16$$$. $$$a_3 - x = 16 - 16 = 0$$$ and $$$a_4 - x = 19 - 16 = 3$$$. Array $$$a$$$ will become equal to $$$[4, 7, 0, 3]$$$.  Operation with indices $$$\{2, 4\}$$$: $$$x = a_2 ~ \& ~ a_4$$$ $$$=$$$ $$$7 ~ \& ~ 3 = 3$$$. $$$a_2 - x = 7 - 3 = 4$$$ and $$$a_4 - x = 3 - 3 = 0$$$. Array $$$a$$$ will become equal to $$$[4, 4, 0, 0]$$$.  Operation with indices $$$\{1, 2\}$$$: $$$x = a_1 ~ \& ~ a_2$$$ $$$=$$$ $$$4 ~ \& ~ 4 = 4$$$. $$$a_1 - x = 4 - 4 = 0$$$ and $$$a_2 - x = 4 - 4 = 0$$$. Array $$$a$$$ will become equal to $$$[0, 0, 0, 0]$$$. Formal definition of bitwise AND:Let's define bitwise AND ($$$\&$$$) as follows. Suppose we have two non-negative integers $$$x$$$ and $$$y$$$, let's look at their binary representations (possibly, with leading zeroes): $$$x_k \dots x_2 x_1 x_0$$$ and $$$y_k \dots y_2 y_1 y_0$$$. Here, $$$x_i$$$ is the $$$i$$$-th bit of number $$$x$$$, and $$$y_i$$$ is the $$$i$$$-th bit of number $$$y$$$. Let $$$r = x ~ \& ~ y$$$ is a result of operation $$$\&$$$ on number $$$x$$$ and $$$y$$$. Then binary representation of $$$r$$$ will be $$$r_k \dots r_2 r_1 r_0$$$, where:$$$$$$ r_i = \begin{cases} 1, ~ \text{if} ~ x_i = 1 ~ \text{and} ~ y_i = 1 \\ 0, ~ \text{if} ~ x_i = 0 ~ \text{or} ~ y_i = 0 \end{cases} $$$$$$

Sample Inputs:
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

Sample Outputs:
1 2 4
1 2
1
1
1 2 3 4 5

Solution (Python):
import sys
input = sys.stdin.readline

def divisors(n):
    if n == 1:
        return [1]
    l = []
    for i in range(1, n // 2 + 1):
        if n % i == 0:
            l += [i]
    return l + [n]
d = {}
for _ in range(int(input())):
    n = int(input())
    a = [int(i) for i in input().split()]
    u = set([x.count('1') for x in zip(*(f'{x:031b}' for x in a))])
    res = []
    for el in u:
        if el == 0:
            continue
        if el in d:
            div = d[el]
        else:
            div = divisors(el)
            d[el] = div
        if res == []:
            res = div.copy()
            continue
        new = []
        for f in res:
            if f in div:
                new += [f]
        res = new.copy()
    if res == []:
        res = [i for i in range(1, n + 1)]
    print(*res, sep=' ')

Solution (Python):
def divisors(n):
    if n == 1:
        return [1]
    l = []
    for i in range(1, n // 2 + 1):
        if n % i == 0:
            l += [i]
    return l + [n]
d = {}
for _ in range(int(input())):
    n = int(input())
    a = [int(i) for i in input().split()]
    u = set([x.count('1') for x in zip(*(f'{x:031b}' for x in a))])
    res = []
    for el in u:
        if el == 0:
            continue
        if el in d:
            div = d[el]
        else:
            div = divisors(el)
            d[el] = div
        if res == []:
            res = div.copy()
            continue
        new = []
        for f in res:
            if f in div:
                new += [f]
        res = new.copy()
    if res == []:
        res = [i for i in range(1, n + 1)]
    print(*res, sep=' ')

Solution (Python):
from collections import defaultdict
import math

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if a.count(0) == n:
        print(' '.join(map(str, range(1, n + 1))))
        return
    counts = defaultdict(int)
    for ele in a:
        b = bin(ele)[2:][::-1]
        for i in range(len(b)):
            if b[i] == '1':
                counts[i] += 1
    gcd = 0
    for val in counts.values():
        if not gcd:
            gcd = val
        else:
            gcd = math.gcd(gcd, val)
    (divisors, i) = ([], 2)
    for i in range(1, gcd + 1):
        if not gcd % i:
            divisors.append(i)
        i += 1
    print(' '.join(map(str, divisors)))
for i in range(int(input())):
    solve()