1918C.md (1515B)
1 Source: https://codeforces.com/problemset/problem/1918/C 2 3 C. XOR-distance 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 integers $a$, $b$, $r$. Find the smallest value of $|({a \oplus x}) - ({b \oplus x})|$ among all $0 \leq x \leq r$. 22 23 $\oplus$ is the operation of [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR), and $|y|$ is [absolute value](https://en.wikipedia.org/wiki/Absolute_value) of $y$. 24 25 Input 26 27 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 28 29 Each test case contains integers $a$, $b$, $r$ ($0 \le a, b, r \le 10^{18}$). 30 31 Output 32 33 For each test case, output a single number — the smallest possible value. 34 35 Example 36 37 Input 38 39 ``` 40 10 41 42 4 6 0 43 44 0 3 2 45 46 9 6 10 47 48 92 256 23 49 50 165 839 201 51 52 1 14 5 53 54 2 7 2 55 56 96549 34359 13851 57 58 853686404475946 283666553522252166 127929199446003072 59 60 735268590557942972 916721749674600979 895150420120690183 61 ``` 62 63 Output 64 65 ``` 66 2 67 1 68 1 69 164 70 542 71 5 72 3 73 37102 74 27934920819538516 75 104449824168870225 76 ``` 77 78 Note 79 80 In the first test, when $r = 0$, then $x$ is definitely equal to $0$, so the answer is $|{4 \oplus 0} - {6 \oplus 0}| = |4 - 6| = 2$. 81 82 In the second test: 83 84 * When $x = 0$, $|{0 \oplus 0} - {3 \oplus 0}| = |0 - 3| = 3$. 85 * When $x = 1$, $|{0 \oplus 1} - {3 \oplus 1}| = |1 - 2| = 1$. 86 * When $x = 2$, $|{0 \oplus 2} - {3 \oplus 2}| = |2 - 1| = 1$. 87 88 Therefore, the answer is $1$. 89 90 In the third test, the minimum is achieved when $x = 1$.