問題一覧 > 通常問題

No.2067 ±2^k operations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : とりゐとりゐ / テスター : 遭難者遭難者 ygussanyygussany karinohitokarinohito
0 ProblemId : 8443 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-02 02:08:55

問題文

$n$ を正整数とします．$X=n$ から始めて，以下の操作を繰り返すことによって $X=0$ にするために必要な最小の操作回数を $f(n)$ とします．

  • 非負整数 $k$ および演算子 $+,-$ のいずれかを選ぶ．
    • 演算子が $+$ のとき，$X$ を $X+2^k$ で置き換える．
    • 演算子が $-$ のとき，$X$ を $X-2^k$ で置き換える．
正整数 $N$ が与えられるので $\displaystyle \sum_{n=1}^N f(n)$ を求めてください．

$T$ 個のテストケースが与えられます．

入力

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$
各ケースは以下の形式で与えられます． 
$N$

  • $1\leq T\leq 10^4$
  • $1\leq N\leq 10^{17}$
  • 入力は全て整数である．

出力

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

サンプル

サンプル1
入力
3
3
10
2022
出力
4
16
8342

$f(1),f(2),f(3)$ は次の通りです．

  • $n=1$ のとき，$1$ 回目の操作で $(0,-)$ を選ぶことで $X=0$ とすることができます．よって $f(1)=1$ です．
  • $n=2$ のとき，$1$ 回目の操作で $(1,-)$ を選ぶことで $X=0$ とすることができます．よって $f(2)=1$ です．
  • $n=3$ のとき，$1$ 回目の操作で $(2,-)$ を選ぶことで $X=-1$ とすることができ，$2$ 回目の操作で $(0,+)$ を選ぶことで $X=0$ とすることができます．$1$ 回の操作で $0$ にすることは不可能なため $f(3)=2$ です．
よって，$1$ つ目のテストケースの答えは $f(1)+f(2)+f(3)=1+1+2=4$ です．

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