Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics

Fixed points

Time limit:2.00 s
Memory limit:256 MB

A fixed point for a function $f$ is a value $x$ such that $f(x)=x$.

In this task we focus on the following function:
$$ f(x) = ((a \cdot x) \oplus b) \bmod 2^{64}$$The operator $\oplus$ is the xor operator (written ^ in C++/Java).

Given $a$ and $b$, can you find a fixed point for the function?


The first input line contains an integer $t$: the number of test cases.

After this, there are $t$ lines that describe the test cases. Each line contains two integers $a$ and $b$.

All test cases have been generated so that $a$ and $b$ have been chosen uniformly randomly from the range $0 \ldots 2^{64}-1$.


For each case, output a number $0\leq x\leq 2^{64}-1$ that is a fixed point for the function, or "-" if no such number exists.

If there are several possible solutions, you can output any of them.


2 5
1 1
0 7


For example, in the first test case, $f(3)=((2\cdot3) \oplus 5) \bmod 2^{64}=3$.