D. Сумма единиц до n

Посчитайте суммарное количество единичных битов у всех чисел от $1$ до $n$.

Перебирать все числа нельзя: $n$ до $2 \cdot 10^{17}$. Считаем по битам.

Сколько чисел из $[0, n]$ имеют единицу в бите $i$? Значения этого бита меняются с периодом $2^{i+1}$: сначала $2^i$ нулей, потом $2^i$ единиц. Значит, полных периодов ровно $\left\lfloor \frac{n+1}{2^{i+1}} \right\rfloor$, и каждый даёт $2^i$ единиц; плюс хвост длиной $(n+1) \bmod 2^{i+1}$, из которого единицами заняты все позиции сверх первых $2^i$.

Сумма по всем битам и есть ответ. Стоит это $O(\log n)$.

Про тип. Среднее число единичных битов у числа около $\log_2 n / 2$, то есть при $n = 2 \cdot 10^{17}$ ответ порядка $5.7 \cdot 10^{18}$ — в 32 бита не помещается, в знаковый 64-битный влезает с запасом примерно в полтора раза. Обратите внимание, что при $n = 10^{18}$ ответ был бы около $3 \cdot 10^{19}$ и не поместился бы даже в беззнаковый 64-битный тип; именно поэтому граница в условии такая.

Одна строка содержит число $n$ ($1 \le n \le 2 \cdot 10^{17}$).

Одно число — суммарное количество единичных битов у чисел от 1 до $n$.