/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数 N,K が与えられます。 以下の条件を満たす正整数 X を N と相性の良い数 と呼びます。
- X と N の排他的論理和は、X を N で割ったあまりと等しい。
N と相性の良い数が K 個以上存在するか判定し、存在する場合は N と相性の良い数のうち K 番目に小さい値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
排他的論理和とは
非負整数 A, B の排他的論理和、A\ \mathrm{XOR}\ B は、以下のように定義されます。
- A\ \mathrm{XOR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 1\le T\le 2\times 10^5
- 1\le N,K\le 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
ここで、 \text{case}_i は i 番目のテストケースを意味する。
各テストケースは以下の形式で与えられる。
N K
出力
それぞれのテストケースについて、N と相性の良い数が K 個以上存在するならば K 番目に小さい値を、存在しないならば -1 を出力せよ。
入力例 1
4 2 1 2 2 1 7 20250126 191
出力例 1
2 3 -1 20381694
N=2 の場合について考えます。
- X=1 のとき、 X と N の排他的論理和は 3 、X を N で割ったあまりは 1 です。したがって、 1 は N と相性の良い数ではありません。
- X=2 のとき、 X と N の排他的論理和は 0 、X を N で割ったあまりは 0 です。したがって、 2 は N と相性の良い数です。
- X=3 のとき、 X と N の排他的論理和は 1 、X を N で割ったあまりは 1 です。したがって、 3 は N と相性の良い数です。
よって、 2 と相性の良い数のうち 1 番目に小さい正整数は 2 、2 番目に小さい正整数は 3 です。したがって、 \text{case}_1 の答えは 2 、 \text{case}_2 の答えは 3 です。
Score : 500 points
Problem Statement
You are given two positive integers N and K. A positive integer X is called compatible with N if it satisfies the following condition:
- The bitwise XOR of X and N is equal to the remainder when X is divided by N.
Determine whether there exist at least K such integers X that are compatible with N. If they do exist, find the K-th smallest such integer.
You are given T test cases; solve each of them.
About XOR
The bitwise XOR of nonnegative integers A and B, denoted A\ \mathrm{XOR}\ B, is defined as follows:
- In the binary representation of A\ \mathrm{XOR}\ B, the digit in the 2^k place (for k \geq 0) is 1 if and only if exactly one of A and B has a 1 in the 2^k place in its binary representation. Otherwise, it is 0.
Constraints
- 1 \le T \le 2\times 10^5
- 1 \le N,K \le 10^9
- 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
Here, \text{case}_i denotes the i-th test case.
Each test case is given in the following format:
N K
Output
For each test case, if there exist at least K positive integers that are compatible with N, print the K-th smallest such integer. Otherwise, print -1.
Sample Input 1
4 2 1 2 2 1 7 20250126 191
Sample Output 1
2 3 -1 20381694
Consider the case N=2.
- When X=1, X\ \mathrm{XOR}\ N = 3 and the remainder of X when divided by N is 1. Therefore, 1 is not compatible with N.
- When X=2, X\ \mathrm{XOR}\ N = 0 and the remainder of X when divided by N is 0. Therefore, 2 is compatible with N.
- When X=3, X\ \mathrm{XOR}\ N = 1 and the remainder of X when divided by N is 1. Therefore, 3 is compatible with N.
Hence, among the numbers that are compatible with 2, the smallest is 2 and the second smallest is 3. Therefore, the answer to \text{case}_1 is 2 and the answer to \text{case}_2 is 3.