問題一覧 > 通常問題

No.2939 Sigma Popcount Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 120
作問者 : kazuppakazuppa / テスター : Yoyoyo8128Yoyoyo8128 yuusaanyuusaan hirayuu_ychirayuu_yc
0 ProblemId : 11348 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-18 17:23:42

問題文

$T$ 個のテストケースが与えられます。順番に処理してください。

$k$ 番目のテストケースは次のようになっています。

  • ある整数 $N_k$ が与えられます。

    • $\ \ \ \ $以下の式の答えを求めてください。

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

    なお、 $\text{popcount}(x)$ とは $x$ を2進表記したときの $1$ の個数を表します。

    入力

    入力は以下の形式で標準入力から与えられる。 
    $T$
$N_1$
$N_2$
.
.
.
$N_{T}$

    制約

    • $1\leq T \leq 10^5$
    • $1\leq N_k\leq 10^{12}\ (1\leq k\leq T)\\$
    • 入力はすべて整数

    出力

    $T$ 行出力してください。

    $k$ 行目には $\sum_{i=1}^{N_k} \text{popcount}(i)$ を一行に出力してください。

    最後に改行してください。

    サンプル

    サンプル1
    入力
    2
5
3
    出力
    7
4

    $\text{popcount}(1)=1,\ \text{popcount}(2)=1,\ \text{popcount}(3)=2,\ \text{popcount}(4)=1,\ \text{popcount}(5)=2$ です。

    なので、 $1$ 番目のテストケースの答えは $1+1+2+1+2=7$ です。

    そして、$2$ 番目のテストケースの答えは $1+1+2=4$ です。

    サンプル2
    入力
    1
10
    出力
    17

    サンプル3
    入力
    4
901
483
269
499
    出力
    4313
2116
1063
2216

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