問題一覧 > 通常問題

No.2067 ±2^k operations

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

問題文

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

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

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

入力

TT
case1\mathrm{case}_1
⋮\vdots
caseT\mathrm{case}_T
各ケースは以下の形式で与えられます． 
NN

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

出力

TT 行出力してください．

サンプル

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

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

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

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