Array Elimination (Codeforces 1602C)
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 math
import os
import sys
from io import BytesIO, IOBase
M = 1000000007
import random
import heapq
import threading
import bisect
import time
from functools import *
from collections import *
from itertools import *
BUFSIZE = 8192
import array

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
    return sys.stdin.readline().rstrip('\r\n')

def out(var):
    sys.stdout.write(str(var))

def lis():
    return list(map(int, inp().split()))

def stringlis():
    return list(map(str, inp().split()))

def sep():
    return map(int, inp().split())

def strsep():
    return map(str, inp().split())

def fsep():
    return map(float, inp().split())

def inpu():
    return int(inp())

def build(arr, a, b, st, node):
    if a == b:
        st[node] = arr[a]
        return st[node]
    mid = (a + b) // 2
    st[node] = min(build(arr, a, mid, st, 2 * node + 1), build(arr, mid + 1, b, st, 2 * node + 2))
    return st[node]

def getmin(arr, a, b, l, r, st, node):
    if l > b or r < a:
        return float('inf')
    if l <= a and r >= b:
        return st[node]
    mid = (a + b) // 2
    return min(getmin(arr, a, mid, l, r, st, 2 * node + 1), getmin(arr, mid + 1, b, l, r, st, 2 * node + 2))

def chck(x, y, z):
    if abs(x[0] * (y[1] - z[1]) + y[0] * (z[1] - x[1]) + z[0] * (x[1] - y[1])) > 0:
        return True
    return False
''

def main():
    t = 1
    t = int(input())
    for _ in range(t):
        n = inpu()
        arr = lis()
        if arr.count(0) == n:
            print(*list(range(1, n + 1)))
            continue
        l = [0] * 30
        for i in arr:
            p = 0
            for j in bin(i).replace('0b', '')[::-1]:
                if j == '1':
                    l[p] += 1
                p += 1
        c = 0
        for i in l:
            c = math.gcd(c, i)
        ans = set()
        for i in range(1, int(math.sqrt(c)) + 2):
            if c % i == 0:
                ans.add(i)
                if i != c // i:
                    ans.add(c // i)
        ans = list(ans)
        ans.sort()
        print(*ans)
if __name__ == '__main__':
    ''
    main()

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

def solve():
    n = int(input())
    k = lambda x: bin(int(x))[2:][::-1]
    a = list(map(k, input().split()))
    m = 0
    for i in a:
        m = max(m, len(i))
    c = [0] * m
    for i in a:
        for j in range(len(i)):
            if i[j] == '1':
                c[j] += 1
    s = set(c)
    s = list(s)
    gcd = s[0]
    for i in range(1, len(s)):
        gcd = math.gcd(gcd, s[i])
    for i in range(1, n + 1):
        if gcd % i == 0:
            print(i, end=' ')
    print()
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
import sys

def solve():
    n = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))
    bits = [0] * 30
    for i in range(30):
        cur_long_int = 1 << i
        for num in arr:
            if num & cur_long_int != 0:
                bits[i] += 1
    print(1, end=' ')
    for k in range(1, n):
        flag = True
        for no_of_bit in bits:
            if no_of_bit % (k + 1):
                flag = False
                break
        if flag:
            sys.stdout.write(str(k + 1) + ' ')
    sys.stdout.write('\n')

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()
main()