/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
2^{30} 未満の正整数 C,X が与えられます。
以下の条件を全て満たす正整数 n が存在するか判定し、存在する場合は一つ求めてください。
- 1\le n < 2^{60}
- (n \oplus C) \bmod n=X
ただし、 n \oplus C は n と C のビット単位 \mathrm{XOR} を表します。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 X,Y のビット単位 \mathrm{XOR} 、X \oplus Y は、以下のように定義されます。
- X \oplus Y を二進表記した際の 2^k (k \geq 0) の位の数は、X,Y を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 1\le T\le 2\times 10^5
- 1\le C,X < 2^{30}
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
C X
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、条件を全て満たす n が存在しない場合は -1 を出力せよ。
そうでない場合、条件を全て満たす n を出力せよ。
条件を全て満たす n が複数ある場合、どれを出力しても正答となる。
入力例 1
3 10 6 2 3 777 153
出力例 1
7 -1 208
1 つ目のテストケースについて考えます。
n=7 は (n\oplus C) \bmod n = (7 \oplus 10) \bmod 7 = 13\bmod 7 = 6=X より条件を全て満たすことが分かります。したがって、 1 行目には 7 を出力すると正答となります。
この他にも n=12,18,19 などを出力しても正答となります。
Score : 700 points
Problem Statement
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.
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
Output
Output the answers for each test case in order, separated by newlines.
For each test case, if there does not exist an n that satisfies all conditions, print -1.
Otherwise, print n that satisfies all conditions.
If there are multiple n that satisfy all conditions, any of them will be accepted.
Sample Input 1
3 10 6 2 3 777 153
Sample 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.