D - Bits, be ambitious
問題文
整数 $K,A,B$ が与えられます。集合 $S$ を $K$ の倍数である正整数全体の集合と定義したとき、$\min\limits_{x \in S}\ \lbrace A \times \mathrm{popcount}(x)+ B \times \mathrm{bitlength}(x)\rbrace$ を求めてください。
$\mathrm{popcount}(x)$ とは？
正整数 $x$ に対して、$x$ を $2$ 進数表記したときに $2^i$ の位が $1$ であるような非負整数 $i$ の個数を $\mathrm{popcount}(x)$ と定義します。
例えば、$13$ を $2$ 進数表記すると 1101 なので、$\mathrm{popcount}(13) = 3$ です。
$\mathrm{bitlength}(x)$ とは？
正整数 $x$ に対して、$x$ を $2$ 進数表記したときに $2^i$ の位が $1$ であるような最大の整数 $i$ を用いて、$\mathrm{bitlength}(x)=i+1$ と定義します。
例えば、$13$ を $2$ 進数表記すると 1101 なので、$\mathrm{bitlength}(13) = 4$ です。
制約
- $1 \leq K,A,B \leq 3 \times 10^{5}$
- 入力はすべて整数である
部分点
set1$(10$ 点$)$：$K= 2$ かつ $A,B \leq 1000$set2$(20$ 点$)$：$K,A,B \leq 1000$all$(70$ 点$)$：追加の制約はない
入力
入力は以下の形式で標準入力から与えられます。
$K$ $A$ $B$
出力
答えを出力してください。
2 252 886
2024
この入力例は部分点 set1 , set2 の制約を満たします。
13 1 10
43
$x = 13$ のとき、$A \times \mathrm{popcount}(x)+ B \times \mathrm{bitlength}(x) = 43$ です。$x$ を $13$ の倍数である正整数のどの値にしても $A \times \mathrm{popcount}(x)+ B \times \mathrm{bitlength}(x)$ は $43$ 未満になりません。
この入力例は部分点 set2 の制約を満たします。
13 10 1
27
この入力例は部分点 set2 の制約を満たします。
181549 300000 1
600083
$x = 181549 \times 26635802336881595045 = 2^{82}+1$ とすると、$A \times \mathrm{popcount}(x)+ B \times \mathrm{bitlength}(x) = 600083$ です。
$181549$ の倍数で、「$2^{82}$ 以下かつ $\mathrm{popcount}$ が $2$ 以下」または「 $\mathrm{popcount}$ が $1$ 以下」を満たす正整数は存在しません。
31415 92653 58979
1651214
300000 300000 300000
8100000