C - てんびんばかり /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

あなたは天秤を用いて物体の重さを 1 g単位で量りたいと考えています。

あなたは N 種類の分銅をそれぞれ K 個ずつ用意することができます。 ここで、i (1 \leq i \leq N) 種類目の分銅は全部同じ重さです。

これらの N \times K 個の分銅をあなたは

  • 天秤の右の皿へ置く
  • 天秤の左の皿へ置く
  • どちらにも置かない

のいずれかを行うことができます。 重さを量りたい物体を右の皿に乗せることとして、

(左の皿に乗った分銅の重さの合計) = (右の皿の乗った分銅の重さの合計) + (物体の重さ)

が成り立つとき天秤は釣り合い、このとき物体の重さは (左の皿に乗った分銅の重さの合計) - (右の皿の乗った分銅の重さの合計) gであると量ることができます。

あなたは分銅をできるだけ少ない種類数用意することで 1 gから M gまでの全ての重さを 1 g単位で量りたいです。 そのような種類数 N を出力してください。

制約

  • 1 \leq M \leq 10^9
  • 1 \leq K \leq 10^5
  • 入力は全て整数である。

入力

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

M K

出力

最小の分銅の種類数 N を出力せよ。


入力例 1

5 1

出力例 1

3

例えば 1,\ 2,\ 3 gの分銅を用意すると、

  • 左の皿に 1 gの分銅を乗せることで 1 g
  • 左の皿に 2 gの分銅を乗せることで 2 g
  • 左の皿に 3 gの分銅を乗せることで 3 g
  • 左の皿に 2,\ 3 gの分銅を、右の皿に 1 gの分銅を乗せることで 4 g
  • 左の皿に 2,\ 3 gの分銅を乗せることで 5 g

を量ることができます。2 種類の分銅では1 \sim 5 gを量ることはできないのでこれが最小です。


入力例 2

8 2

出力例 2

2

例えば 1,\ 3 gの分銅を用意すればよいです。