[BOJ | 백준] 10464번: XOR

by Kimcoding on 2020-03-31 05:20

in BOJ

문제 설명

BOJ 10464

A ~ B의 모든 정수를 XOR한 값을 구하는 문제입니다.

풀이

수학 문제입니다

깔끔하게 수식을 정리하고 싶었는데 실패했습니다! 히힣

주제에 맞게 행동하겠습니다…ㅠ

XOR을 한 값이므로 A ~ B의 수에서 각 자리마다 1이 홀수 개가 있는지, 짝수 개가 있는지 확인하면 됩니다.

A ~ B를 모두 확인할 수 없으니 1이 처음 등장하는 수를 먼저 구합니다.

처음 등장하는 수 ~ B에서 1의 개수를 구하고 처음 등장하는 수 ~ A-1에서 1의 개수를 구하여

A ~ B의 1의 개수가 홀수인지 짝수인지 구할 수 있습니다.

자세한 수식은 밑 코드를 참고해주세요!

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

int main() {
	FIO;
	int t; cin >> t; while (t--) {
		int a, b; cin >> a >> b;
		int ans = 0;
		FOR(i, 0, 29) {
			int x = 1 << i;
			int y = 1 << (i + 1);
			if (x > b) break;
            		// B까지의 1의 홀짝
			int z = ((b - x + 1) / y * x + min((b - x + 1) % y, x)) & 1;
			if (x <= a)
               			z ^= (a - x) / y * x + min((a - x) % y, x); // A~B의 1의 홀짝
			if (z & 1)
                		ans += (1 << i);
		}
		cout << ans << '\n';
	}
	return 0;
}