2085C.md (1548B)
1 Source: https://codeforces.com/problemset/problem/2085/C 2 3 C. Serval and The Formula 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two positive integers $x$ and $y$ ($1\le x, y\le 10^9$). 22 23 Find a non-negative integer $k\le 10^{18}$, such that $(x+k) + (y+k) = (x+k)\oplus (y+k)$ holds$^{\text{∗}}$, or determine that such an integer does not exist. 24 25 $^{\text{∗}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 The only line of each test case contains two integers $x$ and $y$ ($1\le x, y\le 10^9$) — the given integers. 32 33 Output 34 35 For each test case, output a single integer $k$ ($0\le k\le 10^{18}$) — the integer you found. Print $-1$ if it is impossible to find such an integer. 36 37 If there are multiple answers, you may print any of them. 38 39 Example 40 41 Input 42 43 ``` 44 5 45 46 2 5 47 48 6 6 49 50 19 10 51 52 1024 4096 53 54 1198372 599188 55 ``` 56 57 Output 58 59 ``` 60 0 61 -1 62 1 63 1024 64 28 65 ``` 66 67 Note 68 69 In the first test case, since $(2 + 0) + (5 + 0) = (2 + 0) \oplus (5 + 0) = 7$, $k=0$ is a possible answer. Note that $k=4$ is also a possible answer because $(2 + 4) + (5 + 4) = (2 + 4) \oplus (5 + 4) = 15$. 70 71 In the second test case, $(x+k)\oplus (y+k) = (6+k)\oplus (6+k) = 0$. However, $(x+k)+(y+k) \gt 0$ holds for every $k \ge 0$, implying that such an integer $k$ does not exist.