codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1775C.md (1784B)


      1 Source: https://codeforces.com/problemset/problem/1775/C
      2 
      3 C. Interesting Sequence
      4 
      5 time limit per test
      6 
      7 1 second
      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 Petya and his friend, robot Petya++, like to solve exciting math problems.
     22 
     23 One day Petya++ came up with the numbers $n$ and $x$ and wrote the following equality on the board: $$n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,$$ where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Then he suggested his friend Petya find such a minimal $m$ ($m \ge n$) that the equality on the board holds.
     24 
     25 Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer.
     26 
     27 Can you solve this difficult problem?
     28 
     29  ![](https://espresso.codeforces.com/4a5e1ab1c08f0400bd260e438330e662751bdc07.png)
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows.
     34 
     35 The only line of each test case contains two integers $n$, $x$ ($0\le n, x \le 10^{18}$).
     36 
     37 Output
     38 
     39 For every test case, output the smallest possible value of $m$ such that equality holds.
     40 
     41 If the equality does not hold for any $m$, print $-1$ instead.
     42 
     43 We can show that if the required $m$ exists, it does not exceed $5 \cdot 10^{18}$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 10 8
     53 
     54 10 10
     55 
     56 10 42
     57 
     58 20 16
     59 
     60 1000000000000000000 0
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 12
     67 10
     68 -1
     69 24
     70 1152921504606846976
     71 ```
     72 
     73 Note
     74 
     75 In the first example, $10\ \&\ 11 = 10$, but $10\ \&\ 11\ \&\ 12 = 8$, so the answer is $12$.
     76 
     77 In the second example, $10 = 10$, so the answer is $10$.
     78 
     79 In the third example, we can see that the required $m$ does not exist, so we have to print $-1$.