配点: $300$ 点

問題文

AtCoder ではたびたび、次のような形式の問題が出題されています。

答えを $998244353$ で割った余りを求めよ。

ところで、実は $998244353 = 119 \times 2^{23} + 1$ という性質があります。それに関連して、次の問いに答えてください。

整数 $N$ が与えられる。 $N = a \times 2^b + c$ を満たす非負整数の組 $(a, b, c)$ のうち、$a + b + c$ が最小となるものにおける $a + b + c$ の値を出力せよ。

制約

• $1 \leq N \leq 10^{18}$
• $N$ は整数

入力

入力は以下の形式で標準入力から与えられます。

$N$

出力

答えを出力してください。

998244353

143

$998244353 = 119 \times 2^{23} + 1$ であるため、$(a, b, c) = (119, 23, 1)$ のとき等式 $N = a \times 2^{b} + c$ が成り立ちます。 そのときの $a+b+c$ の値は $143$ です。 $a+b+c \leq 142$ となるような組は存在しないため、$143$ と出力すれば正解となります。

1000000007

49483

$1000000007 = 30517 \times 2^{15} + 18951$ であるため、$(a, b, c) = (30517, 15, 18951)$ のとき等式 $N = a \times 2^{b} + c$ が成り立ちます。 そのときの $a+b+c$ の値は $49483$ です。 $a+b+c \leq 49482$ となるような組は存在しないため、$49483$ と出力すれば正解となります。

1

1

$2^0 = 1$ であることに注意してください。

998984374864432412

2003450165