Mod of XOR

AtCoder

IDarc208_c

Time2000ms

Memory256MB

Difficulty—

You are given positive integers $C$ and $X$ that are less than $2^{30}$. Determine whether there exists a positive integer $n$ that satisfies all of the following conditions, and if it exists, find one such $n$. * $1\le n < 2^{60}$ * $(n \oplus C) \bmod n=X$ Here, $n \oplus C$ denotes the bitwise $\mathrm{XOR}$ of $n$ and $C$. You are given $T$ test cases, solve each of them. What is bitwise $\mathrm{XOR}$?The bitwise $\mathrm{XOR}$ of non-negative integers $X$ and $Y$, $X \oplus Y$, is defined as follows: * When $X \oplus Y$ is written in binary, the digit in the $2^k$ place ($k \geq 0$) is $1$ if exactly one of the digits in the $2^k$ place of $X$ and $Y$ written in binary is $1$, and $0$ otherwise. For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$). ## Constraints * $1\le T\le 2\times 10^5$ * $1\le C,X < 2^{30}$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ Each test case is given in the following format: $C$ $X$ [samples]

Samples

Input #1

Output #1

7
-1
208

Consider the first test case.
$n=7$ satisfies all conditions because $(n\oplus C) \bmod n = (7 \oplus 10) \bmod 7 = 13\bmod 7 = 6=X$. Therefore, printing $7$ on the first line will be accepted.
Other than this, printing $n=12,18,19$ etc. will also be accepted.

API Response (JSON)

{
  "problem": {
    "name": "Mod of XOR",
    "description": {
      "content": "You are given positive integers $C$ and $X$ that are less than $2^{30}$. Determine whether there exists a positive integer $n$ that satisfies all of the following conditions, and if it exists, find on",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc208_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given positive integers $C$ and $X$ that are less than $2^{30}$.\nDetermine whether there exists a positive integer $n$ that satisfies all of the following conditions, and if it exists, find on...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments