[BOJ] 25306 - 연속 XOR

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

BOJ - 연속 XOR

문제 유형: 수학, 비트마스킹

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 1024MB

 

문제

준원이는 다음과 같이 A에서 B까지의 자연수들을 나열했다.

 A, A+1, A+2, \dots, B-2, B-1, B

이 수들에 모두 비트 XOR을 취한 값을 구하라.

 

입력

두 자연수 A, B가 공백을 사이에 두고 주어진다.

 

출력

A 이상 B 이하인 모든 자연수들을 XOR한 값을 구하여라.

 

풀이

물론 일일이 구하면 TLE에 걸린다.

대신, f(x)를 1 ... x까지의 XOR sum이라고 해보자.

 

최종적으로 f(b) ^ f(a-1)을 구하면 되는 것이다.

 

f(x), 즉 1 ... x의 XOR sum은 다음처럼 간단한 규칙을 가진다:

mod = x % 4라고 하자.

mod == 0인경우, x이다.

mod == 1인경우, 1이다.

mod == 2인경우, x+1이다.

mod == 3인경우, 0이다.

 

코드

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

var reader *bufio.Reader
var writer *bufio.Writer

func main() {
	reader = bufio.NewReader(os.Stdin)
	writer = bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var a, b int64
	fmt.Fscan(reader, &a, &b)

	ans := getXORSum(b) ^ getXORSum(a-1)
	fmt.Fprintln(writer, ans)
}

func getXORSum(n int64) int64 {
	mod := n % 4
	if mod == 0 {
		return n
	} else if mod == 1 {
		return 1
	} else if mod == 2 {
		return n + 1
	} else {
		return 0
	}
}