2053C.md (2842B)
1 Source: https://codeforces.com/problemset/problem/2053/C 2 3 C. Bewitching Stargazer 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 I'm praying for owning a transparent heart; as well as eyes with tears more than enough... 22 23 — Escape Plan, [Brightest Star in the Dark](https://www.youtube.com/watch?v=GPnymcrXgX0) 24 25 Iris looked at the stars and a beautiful problem emerged in her mind. She is inviting you to solve it so that a meteor shower is believed to form. 26 27 There are $n$ stars in the sky, arranged in a row. Iris has a telescope, which she uses to look at the stars. 28 29 Initially, Iris observes stars in the segment $[1, n]$, and she has a lucky value of $0$. Iris wants to look for the star in the middle position for each segment $[l, r]$ that she observes. So the following recursive procedure is used: 30 31 * First, she will calculate $m = \left\lfloor \frac{l+r}{2} \right\rfloor$. 32 * If the length of the segment (i.e. $r - l + 1$) is even, Iris will divide it into two equally long segments $[l, m]$ and $[m+1, r]$ for further observation. 33 * Otherwise, Iris will aim the telescope at star $m$, and her lucky value will increase by $m$; subsequently, if $l \neq r$, Iris will continue to observe two segments $[l, m-1]$ and $[m+1, r]$. 34 35 Iris is a bit lazy. She defines her laziness by an integer $k$: as the observation progresses, she will not continue to observe any segment $[l, r]$ with a length strictly less than $k$. In this case, please predict her final lucky value. 36 37 Input 38 39 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows. 40 41 The only line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 2\cdot 10^9$). 42 43 Output 44 45 For each test case, output a single integer — the final lucky value. 46 47 Example 48 49 Input 50 51 ``` 52 6 53 54 7 2 55 56 11 3 57 58 55 13 59 60 5801 6 61 62 8919 64 63 64 8765432 1 65 ``` 66 67 Output 68 69 ``` 70 12 71 18 72 196 73 1975581 74 958900 75 38416403456028 76 ``` 77 78 Note 79 80 In the first test case, at the beginning, Iris observes $[1, 7]$. Since $[1, 7]$ has an odd length, she aims at star $4$ and therefore increases her lucky value by $4$. Then it is split into $2$ new segments: $[1, 3]$ and $[5, 7]$. The segment $[1, 3]$ again has an odd length, so Iris aims at star $2$ and increases her lucky value by $2$. Then it is split into $2$ new segments: $[1, 1]$ and $[3, 3]$, both having a length less than $2$, so no further observation is conducted. For range $[5, 7]$, the progress is similar and the lucky value eventually increases by $6$. Therefore, the final lucky value is $4 + 2 + 6 = 12$. 81 82 In the last test case, Iris finally observes all the stars and the final lucky value is $1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028$.