SRM546 Div1 Easy

250

本番では解けなかった。

2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。

なぜ気が付かなかった・・・。

lli f(lli K, lli m)
{
  if (K == 0LL) return m + 1;
  if (m < 0) return 0;

  lli ret = 0;

  bool even = (K % 2 == 0);

  for (lli i = 0; ; ++i) {
    lli mn = K << i;
    lli mx = (K << i) + (1LL << (i + even)) - 1;
    if (m < mn) break;
    ret += min(m, mx) - mn + 1;
  }

  return ret;
}

class KleofasTail {
public:
  long long countGoodSequences(long long K, long long A, long long B)
  {
    lli a = f(K, A - 1);
    lli b = f(K, B);

    return b - a;
  }
};