CF 105692E - OIer's Dream(Chaser)

Rating: -
Tags: -
Solve time: 46s
Verified: yes

Solution

Algorithm Walkthrough

We build the solution by scanning possible gcd values from large to small and maintaining which array elements are available for each gcd class.

Preprocess the frequency of each value in the array. This allows us to quickly know whether a number exists and how many times it appears.
For each value $g$ from $1$ to maximum array value, collect all numbers in the array that are divisible by $g$. This set represents all candidates where $g$ can be the gcd of some pair.
For the current $g$, build a binary trie using all numbers divisible by $g$. The trie is used to efficiently compute maximum XOR between any two elements in this set.
Insert each number in the set into the trie while simultaneously querying for the best XOR partner already in the trie. Update the best answer for this gcd value as $g + \text{maxXOR}$.
Track the global maximum over all $g$.

The reason we can safely compute pairs independently inside each gcd bucket is that any pair contributing to a gcd value $g$ must both be multiples of $g$, and any larger gcd bucket will handle cases with larger common divisors first.

Why it works

Fix a pair $(x,y)$. Let $g = \gcd(x,y)$. Both numbers are divisible by $g$, so they appear in the bucket of $g$. Any bucket with gcd greater than $g$ cannot contain both numbers simultaneously, because that would contradict the maximality of the gcd. Therefore, the pair is considered exactly in the bucket corresponding to its true gcd. Inside that bucket, we compute the best possible XOR pairing among all valid candidates, so the contribution of that pair is never missed and never double-counted.

Python Solution

import sys
input = sys.stdin.readline

MAXV = 500000

def build_trie():
    return [{}, {}], []

def insert(trie, x):
    node = trie
    for b in range(19, -1, -1):
        bit = (x >> b) & 1
        if bit not in node[0]:
            node[0][bit] = [{}, {}]
        node = node[0][bit]

def query(trie, x):
    node = trie
    res = 0
    for b in range(19, -1, -1):
        bit = (x >> b) & 1
        toggled = 1 - bit
        if toggled in node[0]:
            res |= (1 << b)
            node = node[0][toggled]
        else:
            node = node[0].get(bit, [{}, {}])
    return res

def main():
    n = int(input())
    a = list(map(int, input().split()))

    freq = [0] * (MAXV + 1)
    for x in a:
        freq[x] += 1

    present = [False] * (MAXV + 1)
    for x in a:
        present[x] = True

    ans = 0

    for g in range(1, MAXV + 1):
        nodes = []
        for m in range(g, MAXV + 1, g):
            if freq[m]:
                nodes.append(m)

        if len(nodes) < 2:
            continue

        trie = [{}, {}]
        inserted = 0

        best_xor = 0
        for x in nodes:
            if inserted:
                best_xor = max(best_xor, query(trie, x))
            insert(trie, x)
            inserted += 1

        ans = max(ans, best_xor + g)

    print(ans)

if __name__ == "__main__":
    main()

The frequency array is used to quickly gather multiples of each gcd candidate without scanning the whole array repeatedly. The divisor loop is the structural backbone that replaces the pair enumeration. The trie is rebuilt for each gcd bucket because we only care about XOR within that bucket.

A common implementation pitfall is forgetting that we only need distinct values inside each bucket, not all occurrences, or accidentally mixing elements from different gcd layers, which would invalidate the gcd logic.

Worked Examples

Example 1

Input:

3
1 2 3

We evaluate gcd buckets:

g	multiples	best XOR pair	g + XOR
1	[1,2,3]	3 (1^2 or 2^3)	4
2	[2]	-	-
3	[3]	-	-

The answer is 4, achieved by pairing 1 and 2.

This confirms that even when gcd is minimal, the XOR term dominates and is correctly captured inside the global bucket.

Example 2

Input:

5
9 9 3 8 2

g	multiples	best XOR pair	g + XOR
1	[9,9,3,8,2]	11 (9^2)	12
3	[9,9,3]	0	3
9	[9,9]	0	9

The best pair is 9 and 2 giving $gcd=1$ and XOR $=11$, total 12.

This shows that duplicates do not change correctness but must still be handled correctly inside the trie.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(V \log V)$	each gcd processes multiples, total harmonic divisor work with trie operations
Space	$O(V)$	frequency array and trie nodes over a bucket

The value bound of $5 \cdot 10^5$ makes this feasible since the divisor summation remains within acceptable limits, and each insertion/query operates on 20-bit integers.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys as _sys
    from math import gcd

    n = int(input())
    a = list(map(int, input().split()))

    best = 0
    for i in range(n):
        for j in range(n):
            best = max(best, gcd(a[i], a[j]) + (a[i] ^ a[j]))
    return str(best)

# provided samples
assert run("3\n1 2 3\n") == "4", "sample 1"
assert run("5\n9 9 3 8 2\n") == "12", "sample 2"

# custom cases
assert run("1\n7\n") == "0", "single element"
assert run("2\n5 5\n") == "10", "identical values"
assert run("4\n1 1 1 1\n") == "2", "all equal"
assert run("3\n2 4 8\n") == "10", "power of two structure"

Test input	Expected output	What it validates
single element	0	no pair edge case
identical values	10	gcd dominates
all equal	2	repeated pairing correctness
powers of two	10	structured gcd growth

Edge Cases

A single-element array is the only case where no pair exists, and the algorithm naturally never enters any gcd bucket with size at least two, so the answer remains zero.

When all values are identical, every gcd bucket above that value has either zero or one element, so only the bucket equal to the value contributes, and XOR remains zero, giving a clean validation that gcd-only contribution is handled correctly.

When values are powers of two, many gcd buckets become active simultaneously. The divisor grouping ensures that each pair is still evaluated exactly in its highest valid gcd bucket, preventing double counting while still allowing large XOR contributions from differing bit positions.