SRM543 Div1 Easy - EllysXors

問題

L xor L+1 xor L+2 xor ... xor r を求めよ

1 <= L <= r <= 4*10^9

解法

実験すると↓のコードのような法則があることがわかる

class EllysXors {
public:
	ll x(ll n) {
		if (n%4==0) return n;
		if (n%4==1) return 1;
		if (n%4==2) return n+1;
		return 0;
	}

	ll getXor(ll l, ll r) {
		return x(r)^x(l-1);
	}
};