题目描述
Problem Description
Chino has just learned about a data structure called Segment Tree. However, she encounters a problem while writing the Segment Tree: she doesn't know how much space to allocate, only that the number of leaf nodes \( n \) is a positive integer within the range \([a, b]\).
Chino defines \( f(n) \) as the maximum array index occupied by a Segment Tree with \( n \) leaf nodes. She believes that if she knows
\[ \sum_{n=a}^{b} f(n) \]
she can calculate how much space she needs. Therefore, she seeks your help.
Specifically, Chino's pseudocode for building the Segment Tree is as follows:
\[ \def\b#1{\textbf{#1}}\def\t#1{\text{#1}}\def\s\qquad\def\P{\mathbb P}\def\l{\underline{\kern{300pt}}}\def\m#1{#1&\,} \def\if#1{\b{if }#1\b{ then}}\def\endfunc{\b{end function}.}\def\endif{\b{end if}.}\def\func{\b{function}}\def\return{\b{return}} \begin{aligned}&\l\\&\b{Function: }\t{Build a Segment Tree.}\\[-10pt]&\l\\[-5pt]&\begin{array}{r|l}\\[-9pt] \m1\func\ \t{BuildSegmentTree}\left(x,l,r\right):\\ \m2\s\if{\left(l\ne r\right)}:\\ \m3\s\s m\gets\left\lfloor\left(l+r\right)/2\right\rfloor.\\ \m4\s\s\t{BuildSegmentTree}\left(2x,l,m\right).\\ \m5\s\s\t{BuildSegmentTree}\left(2x+1,m+1,r\right).\\ \m6\s\endif\\ \m7\endfunc\\[-10pt]\\\end{array}\\[-13pt]&\l\end{aligned} \]
The maximum array index occupied by the Segment Tree is the maximum value of the parameter \( x \) in all calls to \( \t{BuildSegmentTree} \) after \( \t{BuildSegmentTree}\left(1,1,n\right) \).
Input Format
The input consists of two lines.
The first line contains a positive integer \( a \); the second line contains a positive integer \( b \). Their meanings are as described in the problem statement.
Output Format
Output a single positive integer, representing your answer.
Sample Input and Output
Sample Input #1
1
10
Sample Output #1
108
Sample Input #2
233333
666666
Sample Output #2
588544964910
Sample Input #3
1
1000000000000000000
Sample Output #3
1419691012023749904603586777179575510
Notes/Hints
Sample Explanation #1
The maximum indices for Segment Trees with \( 1 \sim 10 \) leaf nodes are \( 1, 3, 5, 7, 9, 13, 13, 15, 17, 25 \), respectively. Summing these values gives \( 108 \).
Test Case Constraints
This problem uses subtask testing.
For all data, \( 1 \le a \le b \le 10^{10^6} \).
The specific restrictions for each subtask are as follows:
| Subtask Number | Score | \( b \le \) | \( a = b \) |
|---|---|---|---|
| 1 | 10 | \( 10^{10^0} \) | \(\times\) |
| 2 | 10 | \( 10^{10^1} \) | \(\times\) |
| 3 | 10 | \( 10^{10^2} \) | \(\times\) |
| 4 | 10 | \( 10^{10^3} \) | \(\surd\) |
| 5 | 10 | \( 10^{10^3} \) | \(\times\) |
| 6 | 10 | \( 10^{10^4} \) | \(\surd\) |
| 7 | 10 | \( 10^{10^4} \) | \(\times\) |
| 8 | 10 | \( 10^{10^5} \) | \(\surd\) |
| 9 | 10 | \( 10^{10^5} \) | \(\times\) |
| 10 | 10 | \( 10^{10^6} \) | \(\times\) |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分