[Kotlin] 백준 25306 : 연속 XOR

문제 링크

25306번: 연속 XOR

---

---

문제 해설

\(A\)와 \(B\)가 최대 \(10^{18}\)이기 때문에 하나씩 차근차근 XOR 연산을 하면 시간 초과가 발생한다. 이 문제를 시간 내에 해결하기 위해선 누적 XOR의 성질을 알 필요가 있다.

 

 

\(1\leq N\leq 100\)인 \(N\)에 대하여 각 구간별로 누적 XOR을 구해보면 다음과 같은 결과를 얻을 수 있다.

1부터 100까지의 각 누적 XOR

결과를 잘 보면 \(N\)을 4로 나눈 나머지의 값에 따라 규칙적으로 결과가 변한다는 것을 알 수 있다.

• 1 → 1
• 2 → \(N+1\)
• 3 → 0
• 0 → \(N\)

이제 1부터 \(N\)까지의 누적 XOR을 \(O(1)\)의 시간 복잡도로 구할 수 있게 되었다. 문제에서 요구하는 \(A\) 이상, \(B\) 이하인 모든 자연수들을 XOR한 결과는 XOR 연산의 성질을 이용하면 쉽게 구할 수 있다. 기본적으로 같은 수로 XOR 연산을 한 결과는 0이 되고, 어떤 수 \(x\)에 0을 XOR 연산 하게되면 그대로 \(x\)가 나오게 된다. 즉, 아래와 같은 식이 성립하게 된다.

$$\begin{align*}(A\bigoplus B)\bigoplus B&=A\bigoplus (B\bigoplus B)\\&=A\bigoplus 0\\&=A\end{align*}$$

따라서, \(f(A..B)\)를 A 이상, B 이하인 모든 자연수들을 XOR한 결과라고 하면 아래 식이 성립하게 된다.

$$f(1..B)=f(1..A-1)\bigoplus f(A..B)$$

여기서 좌변과 우변에 각각 \(f(1..A-1)\)를 XOR 연산하게 되면 아래와 같은 식을 얻게 된다.

$$f(A..B)=f(1..B)\bigoplus f(1..A-1)$$

문제를 해결하기 위한 모든 준비가 끝났다. \(A\) 이상, \(B\) 이하인 모든 자연수를 XOR한 결과는 1부터 \(A-1\)까지의 누적 XOR에 1부터 \(B\)까지의 누적 XOR를 XOR하면 구할 수 있다.

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    val (a, b) = readLine().split(' ').map { it.toLong() }
    print(b.cumulateXOR() xor (a - 1).cumulateXOR())
}

fun Long.cumulateXOR() = when (this % 4) {
    0L -> this
    1L -> 1
    2L -> this + 1
    else -> 0
}