SRM 543 div1 easy: EllysXors
解法
各桁ごとに bit が立っているかを調べます。
2^i の桁が立っているかどうかを調べる時は, i 桁目の bit は 2^(i+1) 周期ごとに現れたり消えたりすることに着目すれば良いです。
別解ですが 4*n, 4*n+1, 4*n+2, 4*n+3 で bit が 0 になることを利用するのが一番賢そうです。
ll cnt(ll x, ll div) { ll p = x/(2*div), q = x%(2*div); ll ret = p*div; ret += (q>=div ? q-div+1 : 0); return ret; } class EllysXors { public: long long getXor(long long L, long long R) { ll ret = 0; for (int i = 0; i <= 32; i++) { ll c = cnt(R, 1ll<<i) - cnt(L-1, 1ll<<i); if (c%2) ret |= 1ll<<i; } return ret; } };