問題一覧 > 通常問題

No.2939 Sigma Popcount Problem

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 134
作問者 : kazuppa / テスター : Yoyoyo8128 yuusaan hirayuu_yc
お気に入りにしたユーザー ProblemId : 11348 / 自分の提出
問題文最終更新日: 2024-10-18 17:23:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 450 (順位表) の他の問題:

Problem Statement

You are given $T$ test cases. Process them in order.

The $k$-th test case is as follows.

  • An integer $N_k$ is given.

    • $\ \ \ \ $Find the value of the following expression.

    $\ \ \ \ \displaystyle\sum_{i=1}^{N_k} \text{popcount}(i)$

    Here, $\text{popcount}(x)$ denotes the number of $1$s in the binary representation of $x$.

    Input

    The input is given from Standard Input in the following format. 
    $T$
$N_1$
$N_2$
.
.
.
$N_{T}$

    Constraints

    • $1\leq T \leq 10^5$
    • $1\leq N_k\leq 10^{12}\ (1\leq k\leq T)\\$
    • All input values are integers.

    Output

    Output $T$ lines.

    On the $k$-th line, output $\sum_{i=1}^{N_k} \text{popcount}(i)$ on a single line.

    Print a newline at the end.

    Sample

    Sample 1
    Input
    2
5
3
    Output
    7
4

    We have $\text{popcount}(1)=1,\ \text{popcount}(2)=1,\ \text{popcount}(3)=2,\ \text{popcount}(4)=1,\ \text{popcount}(5)=2$.

    Therefore, the answer to the $1$-st test case is $1+1+2+1+2=7$.

    And the answer to the $2$-nd test case is $1+1+2=4$.

    Sample 2
    Input
    1
10
    Output
    17

    Sample 3
    Input
    4
901
483
269
499
    Output
    4313
2116
1063
2216

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。