No.737 PopCount
レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 100
作問者 :
ei1333333
/ テスター :
beet
タグ : / 解いたユーザー数 100
作問者 :
ei1333333
/ テスター :
beet
問題文最終更新日: 2018-09-28 01:10:29
問題文
$1$ が大好きな M さんは, ある自然数 $x$ の美しさ $V(x)$ を次のように定義しました。
- $V(x) = x \times popcount(x)$
ここで $popcount(x)$ は $x$ を $2$ 進表記したときに現れる $1$ の数と定義します。例えば $popcount(23) = 4$ です。$23$ を $2$ 進表記すると $10111$ で, これに現れる $1$ の数は $4$ 個です。
自然数 $N$ が与えられるので $\displaystyle \sum_{i=1}^{N} V(i)$ を $10^9+7$ で割った余りで求めてください。
入力
$N$
$1$ 行に自然数 $N(1 \le N \le 10^{18})$ が与えられます。
出力
$1$ 行に答えを出力してください。
サンプル
サンプル1
入力
5
出力
23
$popcount(1) = 1, popcount(2) = 1, popcount(3) = 2, popcount(4) = 1, popcount(5)=2$ です。
$(1 \times 1) + (2 \times 1) + (3 \times 2) + (4 \times 1) + (5 \times 2) = 23$ より $23$ が答えとなります。
サンプル2
入力
30
出力
1333
サンプル3
入力
23072602871
出力
123456789
入力の $N$ が 32bit整数型に収まらない場合があることや, $10^9+7$ で割った余りで出力することに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。