排他的論理和の演算を \(\oplus\) 、あまりを取る演算を \(\text{mod}\) で表すと、条件は \(X\oplus N = X\ \text{mod}\ N\) と書けます。

もし \(X<N\) なら \(X\oplus N = X\ \text{mod}\ N=X\) となり、 \(N=0\) となってしまうので不適です。よって、以降は \(X\geq N\) を仮定します。

ビット毎に考えると \(X\oplus N \geq X-N\) が成立することが分かるので、ここから不等式 \(X\ \text{mod}\ N\geq X-N\) が得られます。

\(X\) を \(N\) で割った時の商を \(X_1\) 、あまりを \(X_2\) とすると（この時 \(X=X_1N+X_2\) が成立します）、この不等式は \(X_2\geq (X_1-1)N+X_2\) となり、式変形することで \(X_1\le 1\) が分かります。これと \(X\geq N\) を用いると、 \(X_1=1\) が必要条件として得られます。\(X_1=1\) は \(N\le X < 2N\) と同値なので、以降はこの条件を仮定します。

\(N\le X < 2N\) という条件下では \(X\ \text{mod}\ N=X-N\) なので、元々の条件の式は \(X\oplus N = X-N\) と表されます。ここで、二進数での引き算と排他的論理和の演算を各ビット毎に考えていくと、 \(k\) ビット目引き算と排他的論理和の演算の振る舞いが異なるのは以下の場合のみであることが分かります。

• \(X\) の \(k\) ビット目が \(0\) で、 \(N\) の \(k\) ビット目が \(1\) である。 … \((\star)\)

具体的には、上の状況下で \(X\oplus N\) の方が \(X-N\) より \(2^{k+1}\) だけ大きくなってしまいます。

\(X\oplus N = X-N\) が成立することは \((\star)\) の条件が成立するような \(k\) が存在しないことと同値になります。これは、 \(X\) が \(N\) のビットを全て包含していることと同じです。

以上をまとめると、 \(X\) が \(N\) と相性の良い数である必要十分条件は

• \(N\le X < 2N\) … \((\text{A})\)
• \(X\) が \(N\) のビットを全て包含している … \((\text{B})\)

であることが分かりました。

最後に \(N\) と相性の良い数のうち \(K\) 番目に小さい値を求める方法を考えます。

まず、 \((\text{B})\) の条件を満たす \(X\) を考えます。 \(N\) の \(k\) ビット目が \(1\) の時 \(X\) の \(k\) ビット目も \(1\) である必要がありますが、 \(N\) の \(k\) ビット目が \(0\) である時は制限はありません。よって、 \(N\) の \(k\) ビット目が \(0\) であるような場所を取り出し、 \(K-1\) を二進数表記した値を順番に入れていくことで \(K\) 番目に小さい値が得られます。ただし、その値が \((\text{A})\) を満たさない場合は答えは -1 となります。

以上で問題が解けました。計算量は各ケース毎に \(O(\log N)\) となります。

実装例(Python3)

for _ in range(int(input())):
    n, k = map(int, input().split())
    k -= 1
    x = n
    z = 0
    for i in range(30):
        while n & (1 << z):
            z += 1
        if k & (1 << i):
            x |= 1 << z
        z += 1
    print(x if x < 2 * n else -1)