10464번: XOR

https://www.acmicpc.net/problem/10464


$O(t)$

f(n)=1^2^3^...^n 이라고 할때
a^(a+1)^(a+2)^ ... ^(b-1)^b = f(a-1)^f(b)이다.
f(n)을 빠르게 구하면 된다.

f(1)...f(n) 구하다보면 다음과 같은 규직을 발견할 수 있다.
n%4==0 -> n
n%4==1 -> 1
n%4==2 -> n+1
n%4==3 -> 0

즉, f(n)은 n을 4로 나눈 나머지에 따라 O(1)에 구할 수 있다.

#include<cstdio>
int f(int x) { return x - x % 2 * x + (x / 2 & 1 ^ x & 1); }
int t, x, y;
int main() {
    scanf("%d", &t);
    while (t--) scanf("%d %d", &x, &y), printf("%d\n", f(x - 1) ^ f(y));
    return 0;
}