[C++] 백준 25306번: 연속 XOR

문제 링크

25306번: 연속 XOR

문제 요약

A, B가 주어질 때, A에서 B까지 XOR한 값을 구해야 한다.

접근 방법

A와 B는 최대 $10^{18}$까지이기 때문에 직접 XOR을 계산하면 TLE를 받을 수밖에 없습니다.

문제를 보자마자 든 생각은, A에서 B까지의 수들을 XOR한 값은 $B ⊕(A - 1)$과 같다는 성질을 이용하면 될 것이라는 생각이었습니다. 이 성질은 과거에 XOR 관련 문제들을 풀었을 때 자주 사용할 일이 있었습니다.

1부터 N까지의 XOR을 구하는 것은 생각보다 간단합니다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int val = 0;
	
	for (int i = 1; i <= 20; i++) {
		val ^= i;
		cout << i << " : " << val << '\n';
	}

	return 0;
}

위와 같이 코드를 작성했을 때,

위와 같은 결과를 얻을 수 있습니다. 보시면, 4로 나눈 나머지가 3에 해당하는 수에서 0이 된다는 것을 확인할 수 있습니다.

따라서 4로 나눈 나머지가 3인 경우에는 0으로 처리하면 됩니다. 그 외의 경우에는 누적 XOR이 0인 부분에서부터 직접 XOR해서 구하면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

long long cum_xor(long long num) {
	switch (num % 4) {
	case 0:
		return num;
	case 1:
		return num ^ (num - 1);
	case 2:
		return num ^ (num - 1) ^ (num - 2);
	case 3:
		return 0;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	long long a, b;
	cin >> a >> b;

	cout << (cum_xor(b) ^ cum_xor(a - 1)) << '\n';
	return 0;
}