SRM546 Div1 Easy - KleofasTail

問題

「xのkleofas tail」とは、1個目の要素がxで、i(>2)個目の要素が
i-1個目の要素=yが偶数のとき) y/2
yが奇数のとき) y-1
であるような長さ無限の数列である
a <= x <= b で↑の数列に1回以上kが登場するようなxの個数を求めよ

0 <= k <= 10^18
0 <= a <= b <= 10^18

解法

kからスタートして逆操作をしていく
kが偶数のときはk*2かk+1へ、奇数のときはk*2へ遷移できる
これを繰り返すと、2進数表記でprefixがkまたはk|1になっているような数は全て作れる
あとはある数x以下で↑のようなものの個数を数えられればいい
これはkを左に1ビットずつシフトしていき、そのシフトした数(=sとする)とxの上位kビットが同じときはx-s+1個、そうでないときは2^(シフト数)個だけ存在する

実装

k=0のときはprefixがどうとかいう話は通じないからb-a+1を返す

class KleofasTail {
public:
	ll cnt(ll k, ll x) {
		ll res = 0;
		rep(i,60) {
			ll s = k<<i;
			if (x<s) break;
			res += min(1ll<<i, x-s+1);
		}
		return res;
	}

	ll countGoodSequences(ll k, ll a, ll b) {
		if (k==0) return b-a+1;
		ll res = cnt(k,b) - cnt(k,a-1);
		if (k%2==0) res += cnt(k+1,b) - cnt(k+1,a-1);
		return res;
	}
};