백준 10464번 XOR

백준 10464번: XOR

아이디어

v[i] = a[1]^a[2]^a[3]^…a[i]라 하자. 이 때 i%4 == 3인 경우 v[i] 가 0이 된다! 또 a[l]^a[l+1]^…a[r-1]^a[r] = v[l-1]^v[r]이다. 이를 이용하면 쉽게 문제를 풀 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

int solve(int x) {
    int start = x/4*4;
    int ret = start;
    while (++start <= x) {
        ret ^= start;
    }
    return ret;
}

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

    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        cout << (solve(a-1)^solve(b)) << '\n';
    }

    return 0;
}

여담

누적합 느낌?