Background

A mathematical spirit of constantly pushing yourself forward — dedication.

"Light of Dedication" Lisa is both a priest of "God of Order" Paila and a believer of "God of Disorder" Dionysus.

Lisa recently studied high-precision division. She can compute division of an $n$-digit integer in $\Theta(n \log n)$ time complexity.

Problem Description

Lisa wants to make a division table for positive integers up to $n$. Specifically, it is a table that records $\lfloor a/b \rfloor$ ($1\leq b \leq a \leq n$, and $a,b$ are both integers). She makes it using the following method:

Enumerate positions $(a,b)$ in increasing order with $a$ as the primary key and $b$ as the secondary key. If position $(a,b)$ is not filled, then:

Compute $\lfloor a/b \rfloor$. The mana cost for this is $d_a \log_2 d_a$ (where $d_a$ is the number of decimal digits of $a$, i.e., $d_a=\lfloor 1+ \log_{10}a\rfloor$). Then enumerate positive integers $i$, and for all not filled positions $(ai,bi)$ ($ai\leq n$), fill them with $\lfloor a/b \rfloor$. Each fill costs mana $d_i$.

Since Mena has already made a multiplication table, Lisa can compute multiplication directly without any mana cost. Now Lisa wants to know how much mana is needed to make the entire division table.

To avoid precision issues, your output is considered correct as long as its relative error from the standard output does not exceed $10^{-6}$. It is guaranteed that the relative error between the standard output and the actual answer does not exceed $10^{-10}$.

Input Format

One line with a positive integer $n$, indicating that you want to make a division table of size $n$.

Output Format

One line with a real number, representing the answer.

6

21.0000000

20

422.0000000

233

99838.0384544

Hint

[Sample $1$ Explanation]

Since $a \leq 6$, $d_a=1$, so $d_a \log_2 d_a=0$. That is, within this range only filling numbers costs mana. Also, each $i$ is at most $6$, so $d_i=1$, and each fill costs a fixed $1$ mana point. Filling all $1+2+3+4+5+6=21$ numbers costs $21$ mana.

Therefore, the answer is $21$.

[Constraints]

This problem uses bundled testdata.

Subtask 1 (15 pts): $n\le 5000$;
Subtask 2 (15 pts): $n\le 10^5$;
Subtask 3 (30 pts): $n\le 2 \times 10^6$;
Subtask 4 (40 pts): no special constraints.

For all testdata, $1\le n \le 2 \times 10^7$.

[Hint]

$\log_2 n$ is read as “the logarithm of $n$ with base $2$”. Let $x=\log_2n$, which means $2^x=n$.

Translated by ChatGPT 5