연속한 수의 XOR sum

ll xorSum(ll n) {
	int m = n % 4;
	if (m == 0) return n;
	if (m == 1) return 1;
	if (m == 2) return n + 1;
	return 0;
}

 

1부터 n까지의 수의 XOR sum은 위와 같다.

 

자세한 내용은 여기에서 볼 수 있다.

 

 

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

 

구간 [L : R] 의 xor 합 역시 같은 두 수를 xor 하면 0이 된다는 사실을 이용하여 구할 수 있다.