GCD is Greater (Codeforces 1945H)
Tags: Math, number theory

In the evenings during the hike, Kirill and Anton decided to take out an array of integers $$$a$$$ of length $$$n$$$ from their backpack and play a game with it. The rules are as follows: Kirill chooses from $$$2$$$ to $$$(n-2)$$$ numbers and encircles them in red. Anton encircles all the remaining numbers in blue. Kirill calculates the greatest common divisor (GCD) of all the red numbers. Anton calculates the bitwise AND of all the blue numbers and adds the number $$$x$$$ to the result. If the GCD of all the red numbers is strictly greater than the sum of the bitwise AND of all the blue numbers and the number $$$x$$$, then Kirill wins; otherwise, Anton wins.Help Kirill to beat Anton or tell if it's impossible.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20\,000$$$) — the number of test cases. Then follows the description of the test cases.The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$4\le n \le 4\cdot 10^5$$$, $$$0 \le x \le 4\cdot 10^5$$$) — the number of integers and the number $$$x$$$ respectively.The second line contains an array $$$a$$$ of length $$$n$$$ ($$$1 \le a_i \le 4\cdot 10^5$$$).It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$4\cdot 10^5$$$. It is also guaranteed that the sum of the maximum values of $$$a_i$$$ for each test case does not exceed $$$4\cdot 10^5$$$.

Output: For each test case, output "YES" on the first line if the condition can be met, on the second line, output the number of chosen numbers by Kirill and the numbers themselves in any order separated by a space, and on the third line, output the size of the second set and the numbers in it.Otherwise, output "NO".You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.


Sample Inputs:
8
4 1
4 3 1 8
4 1
4 5 8 4
5 0
1 1 1 1 1
5 2
31 63 127 63 31
4 1
1 3 3 3
8 3
4 3 4 1 2 2 5 3
4 2
1 4 3 6
8 48
31 61 37 15 53 26 61 12

Sample Outputs:
YES
2 4 8
2 3 1 
YES
2 4 4
2 5 8 
NO
YES
2 63 63
3 31 127 31
YES
2 3 3
2 1 3
YES
2 4 4
6 3 1 2 2 5 3
YES
2 3 6
2 1 4 
YES
2 61 61
6 31 37 15 53 26 12

Solution (Python):
import sys
from math import gcd
input = lambda : sys.stdin.readline().rstrip()

def set_bit(n: int, offset: int) -> int:
    return n | 1 << offset

def test_bit(n: int, offset: int) -> int:
    return n & 1 << offset

def solve_case():
    (n, x_add) = map(int, input().split())
    a = list(map(int, input().split()))
    a_max = max(a)
    n_bits = 19
    cnt_bit_not_set = [0] * n_bits
    idx_bit_not_set = [[-1] * 2 for _ in range(n_bits)]
    for (i, x) in enumerate(a):
        for k in range(n_bits):
            if not x & 1:
                if cnt_bit_not_set[k] < 2:
                    idx_bit_not_set[k][cnt_bit_not_set[k]] = i
                cnt_bit_not_set[k] += 1
            x >>= 1
    to_test = set()
    and_score = 0
    for k in range(n_bits):
        if cnt_bit_not_set[k] == 0:
            and_score = set_bit(and_score, k)
        elif cnt_bit_not_set[k] == 1:
            to_test |= {idx_bit_not_set[k][0]}
        elif cnt_bit_not_set[k] == 2:
            to_test |= {idx_bit_not_set[k][0], idx_bit_not_set[k][1]}
        else:
            pass
    for i in to_test:
        for j in range(n):
            if i != j:
                g = gcd(a[i], a[j])
                and_remain = 0
                for k in range(n_bits - 1, -1, -1):
                    and_remain <<= 1
                    c = n - cnt_bit_not_set[k]
                    if test_bit(a[i], k):
                        c -= 1
                    if test_bit(a[j], k):
                        c -= 1
                    if c == n - 2:
                        and_remain |= 1
                if g > and_remain + x_add:
                    red = [a[i], a[j]]
                    blue = [a[x] for x in range(n) if x != i and x != j]
                    return f"YES\n{2} {' '.join(map(str, red))}\n{n - 2} {' '.join(map(str, blue))}"
    idx = [[] for _ in range(a_max + 1)]
    for (i, x) in enumerate(a):
        idx[x] += [i]
    for x in range(and_score + x_add + 1, a_max + 1):
        red_idx = []
        for y in range(x, a_max + 1, x):
            i = 0
            while len(red_idx) < 2 and i < len(idx[y]):
                if idx[y][i] not in to_test:
                    red_idx += [idx[y][i]]
                i += 1
            if len(red_idx) == 2:
                break
        if len(red_idx) == 2:
            i = red_idx[0]
            j = red_idx[1]
            red = [a[i], a[j]]
            blue = [a[x] for x in range(n) if x != i and x != j]
            return f"YES\n{2} {' '.join(map(str, red))}\n{n - 2} {' '.join(map(str, blue))}"
    return 'NO'
ans = []
for _ in range(int(input())):
    ans += [str(solve_case())]
print('\n'.join(ans))

Solution (Python):
from math import gcd
import sys
input = sys.stdin.readline
K = 20

def solve():
    (n, x) = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    def answer(a, b):
        if a > b:
            (a, b) = (b, a)
        ans = f'YES\n2 {first} {second}\n{n - 2} '
        B = [a, b, 1 << K]
        j = 0
        res = []
        for a in A:
            if a == B[j]:
                j += 1
            else:
                res.append(a)
        ans += ' '.join(map(str, res))
        return ans
    N = A[-1] + 1
    cnt = [0] * N
    bits = [0] * K
    for a in A:
        cnt[a] += 1
        for j in range(K):
            if a >> j & 1 == 0:
                bits[j] += 1
    candidates = set()
    for j in range(K):
        if 1 <= bits[j] <= 2:
            for (i, a) in enumerate(A):
                if a >> j & 1 == 0:
                    candidates.add(i)
    for i in candidates:
        first = A[i]
        for (j, second) in enumerate(A):
            if i == j:
                continue
            g = gcd(first, second)
            if g <= x:
                continue
            y = 0
            for b in range(K):
                tot = 2 - (first >> b & 1) - (second >> b & 1)
                if bits[b] == tot:
                    y |= 1 << b
            if g > y + x:
                return answer(first, second)
    y = 0
    for j in range(K):
        if bits[j] == 0:
            y |= 1 << j
    for i in candidates:
        cnt[A[i]] -= 1
    for i in range(x + 1, N):
        red = []
        for j in range(i, N, i):
            if cnt[j]:
                red.append(j)
                if cnt[j] > 1 and len(red) < 2:
                    red.append(j)
            if len(red) == 2:
                break
        if len(red) == 2:
            (first, second) = red
            g = gcd(first, second)
            if g > y + x:
                return answer(first, second)
    return 'NO'
T = int(input())
out = [solve() for _ in range(T)]
print('\n'.join(map(str, out)))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import math
for _ in range(int(input())):
    (n, x) = map(int, input().split())
    a = sorted(map(int, input().split()))
    N = a[-1] + 1
    C = [0] * N
    BITS = [0] * 20
    for ai in a:
        C[ai] += 1
        for bit in range(20):
            BITS[bit] += ai >> bit & 1
    ans = None
    candidates = set()
    A = 0
    for bit in range(20):
        if n - 2 <= BITS[bit] < n:
            for (i, ai) in enumerate(a):
                if ai >> bit & 1 == 0:
                    candidates.add(i)
        elif BITS[bit] == n:
            A |= 1 << bit
    for i in candidates:
        ai = a[i]
        for (j, aj) in enumerate(a):
            if i == j:
                continue
            gcd = math.gcd(ai, aj)
            _and = 0
            for bit in range(20):
                nb = BITS[bit] - (ai >> bit & 1) - (aj >> bit & 1)
                if nb == n - 2:
                    _and |= 1 << bit
            if gcd > _and + x:
                ans = (ai, aj)
                break
        if ans:
            break
    else:
        for i in candidates:
            C[a[i]] -= 1
        for G in range(A + x + 1, N):
            exists = []
            for m in range(G, N, G):
                if C[m] > 0:
                    exists.append(m)
                if C[m] > 1 and len(exists) < 2:
                    exists.append(m)
                if len(exists) == 2:
                    break
            if len(exists) == 2:
                (u, v) = exists
                gcd = math.gcd(u, v)
                if gcd - A > x:
                    ans = (u, v)
                    break
        for i in candidates:
            C[a[i]] += 1
    if ans:
        oth = []
        for (ai, cnt) in enumerate(C):
            if cnt > 0:
                oth.extend([ai] * (cnt - ans.count(ai)))
        print('YES')
        print(2, *ans)
        print(n - 2, *oth)
    else:
        print('NO')