SRM543 Div1 Easy

250

mod 4 とかいうスマートな解法があるらしい。

unsigned int ならループを回しても間に合うとか間に合わないとか。

lli f(lli n)
{
  lli sum = (n + 1LL) / 2LL % 2;
  for (lli i = 0; i < 63; ++i) {
    if (n < (1LL << i)) break;
    lli a = 1LL << i;
    lli m = (n + 1LL) % a;
    if ((n + 1LL) / a % 2 == 0) continue;
    if (m % 2LL) sum |= a;
  }
  return sum;
}

class EllysXors {
public:
  long long getXor(long long L, long long R)
  {
    return f(R) ^ f(L - 1);
  }
};