Codeforces Round 822 (Div. 2) |
---|
Finished |
Let $$$S$$$ be the Thue-Morse sequence. In other words, $$$S$$$ is the $$$0$$$-indexed binary string with infinite length that can be constructed as follows:
For example, here are the first four iterations:
Iteration | $$$S$$$ before iteration | $$$S$$$ before iteration with flipped bits | Concatenated $$$S$$$ |
1 | 0 | 1 | 01 |
2 | 01 | 10 | 0110 |
3 | 0110 | 1001 | 01101001 |
4 | 01101001 | 10010110 | 0110100110010110 |
$$$\ldots$$$ | $$$\ldots$$$ | $$$\ldots$$$ | $$$\ldots$$$ |
You are given two positive integers $$$n$$$ and $$$m$$$. Find the number of positions where the strings $$$S_0 S_1 \ldots S_{m-1}$$$ and $$$S_n S_{n + 1} \ldots S_{n + m - 1}$$$ are different.
Each test contains multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.
The first and only line of each test case contains two positive integers, $$$n$$$ and $$$m$$$ respectively ($$$1 \leq n,m \leq 10^{18}$$$).
For each testcase, output a non-negative integer — the Hamming distance between the two required strings.
61 15 1034 21173 3419124639 5634877212073412269 96221437021
1 6 95 20 28208137 48102976088
The string $$$S$$$ is equal to 0110100110010110....
In the first test case, $$$S_0$$$ is "0", and $$$S_1$$$ is "1". The Hamming distance between the two strings is $$$1$$$.
In the second test case, $$$S_0 S_1 \ldots S_9$$$ is "0110100110", and $$$S_5 S_6 \ldots S_{14}$$$ is "0011001011". The Hamming distance between the two strings is $$$6$$$.
Name |
---|