SRM546 Div1 250

問題

Xが非負の整数であるとき、以下の性質を持つ無限列をXのKleofas tailという。

• 数列の最初はX
  • 偶数の数字の次の要素は、その数字の半分にしたもの
  • 奇数の数字の次の要素は、その数字から1引いたもの

例えば、X=60の場合は、60,30,15,14,7,6,...となる。
AからBの間の数字で、1度以上数字Kが出現するものの個数を答える。

考え方

逆に1から偶数の時は2倍、奇数の時は2倍にしたものと1を足したものを書き出していってみる。
すると、各数字は1回ずつしかでてこないことがわかる。
さらに2倍していく方は2の累乗で増えていくことから、O(log N)で探索していっている。

与えられるKに対して、上記の操作を繰り返して、A〜Bに当てはまる数をカウント。
K=1,2の場合は、ほぼすべての数字なので、これだけ探索せずにO(1)で返すようにすれば間に合う。