ConstructOR  (Codeforces 1748D)
Tags: Math, chinese remainder theorem

You are given three integers $$$a$$$, $$$b$$$, and $$$d$$$. Your task is to find any integer $$$x$$$ which satisfies all of the following conditions, or determine that no such integers exist:  $$$0 \le x \lt 2^{60}$$$;  $$$a|x$$$ is divisible by $$$d$$$;  $$$b|x$$$ is divisible by $$$d$$$. Here, $$$|$$$ denotes the bitwise OR operation.

Input: Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Each test case consists of one line, containing three integers $$$a$$$, $$$b$$$, and $$$d$$$ ($$$1 \le a,b,d \lt 2^{30}$$$).

Output: For each test case print one integer. If there exists an integer $$$x$$$ which satisfies all of the conditions from the statement, print $$$x$$$. Otherwise, print $$$-1$$$.If there are multiple solutions, you may print any of them. 

Note: In the first test case, $$$x=18$$$ is one of the possible solutions, since $$$39|18=55$$$ and $$$12|18=30$$$, both of which are multiples of $$$d=5$$$.In the second test case, $$$x=14$$$ is one of the possible solutions, since $$$8|14=6|14=14$$$, which is a multiple of $$$d=14$$$.In the third and fourth test cases, we can show that there are no solutions.

Sample Inputs:
8
12 39 5
6 8 14
100 200 200
3 4 6
2 2 2
18 27 3
420 666 69
987654321 123456789 999999999

Sample Outputs:
18
14
-1
-1
0
11
25599
184470016815529983

Solution (Python):
def modinc(a, m):
    (m0, y, x) = (m, 0, 1)
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x += m0
    return x

def crt(v):
    ans = 0
    n = len(v)
    m = 1
    for i in range(n):
        m *= v[i][0]
    for i in range(n):
        t = 1
        for j in range(i):
            t *= v[j][0]
            t *= modinc(v[j][0], v[i][0])
            t %= m
        y = (v[i][1] + m - ans) % m
        ans += t * y % m
        ans %= m
    return ans

def solve():
    (a, b, d) = map(int, input().split())
    for i in range(30):
        x = d >> i
        x = x & 1
        if x:
            break
        else:
            y1 = a >> i
            y2 = b >> i
            y1 = y1 & 1
            y2 = y2 & 1
            if y1 == 1 or y2 == 1:
                print(-1)
                return
    while d % 2 == 0:
        d = d // 2
    p1 = [2 ** 30, a | b]
    p2 = [d, 0]
    v = [p1, p2]
    ans = crt(v)
    print(ans)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
def lsb(x):
    f = 0
    while 1 << f & x == 0:
        f += 1
    return f
t = int(input())
for i in range(t):
    (a, b, d) = map(int, input().split())
    a |= b
    if a % d == 0:
        print(a)
        continue
    f = lsb(d)
    if f > 0 and (a & 2 ** f - 1 != 0 or b & 2 ** f - 1 != 0):
        print(-1)
        continue
    d1 = d // 2 ** f
    inv = pow(2 ** (30 - f), -1, d1)
    assert inv >= 0
    ans = 2 ** (30 - f) * inv - 1 << f
    print(ans)
    assert (a | ans) % d == 0 and (b | ans) % d == 0

Solution (Python):
def ctz(x):
    return (x & -x).bit_length() - 1

def test():
    (a, b, d) = map(int, input().split(' '))
    (o, td) = (a | b, ctz(d))
    if ctz(o) < td:
        print(-1)
        return
    (o2, d2) = (o >> td, d >> td)
    (i, k) = ((d2 + 1) // 2, 1)
    for _ in range(30 - td):
        k = k * i % d2
    k = k * (d2 - o2 % d2) % d2
    r = (k << 30) + o
    assert 0 <= r < 1 << 60
    assert (a | r) % d == 0
    assert (b | r) % d == 0
    print(r)

def main():
    for _ in range(int(input())):
        test()
if __name__ == '__main__':
    main()