[JAVA] 백준 25306 - 연속 XOR

문제

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

25306번: 연속 XOR

해결 방법

• 문제에서 주어진 A, B의 범위가 10^18으로 매우 큼
• 하나씩 XOR 연산을 해서 답을 구하면 시간초과 발생할 것임
• 따라서 시간을 줄일 수 있는 방법을 찾아야 함
• XOR 계산은 두 수가 같으면 0, 다르면 1을 뜻함
• 계산을 몇번 해보다보니 규칙을 하나 발견함
  • 00 xor 01 xor 10 xor 11 의 결과는 항상 0임
  • 그리고 이 앞에 어떤 수가 붙더라도 1이 짝수개 있기 때문에 0일수 밖에 없음
  • ex) 101110010101000 xor 101110010101001 xor 101110010101010 xor 101110010101011 = 0
• 정리해보면
  1. 4~7까지의 xor 결과값 = 0
  2. 8~11까지의 xor 결과값 = 0
  3. 12~15까지의 xor 결과값 = 0
  4. ......
  5. 1000000000000000000~1000000000000000003 까지의 xor 결과값 = 0
• 이라는 사실을 알아냄
• 따라서 이 문제의 해결방법은 입력받은 두 값이 5 321 이라면
• 모두 계산할 필요 없이
• 5 xor 6 xor 7 xor [ 8 xor 9 xor 10 xor ...... xor 318 xor 319 xor ] 320 xor 321
• [ ] 괄호 친 부분을 빼고 나머지 부분만 계산하면 정답
• 5 ~ 321까지의 xor 결과값 = 5 xor 6 xor 7 xor 320 xor 321 = 5

코드

import java.util.Scanner;

public class p25306 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long start = sc.nextLong();
        long end = sc.nextLong();

        long result = start;
        // 임의의 작은 값(10)까지는 일일이 계산
        // 이로써 4의 배수 찾는 과정에서 중복될 일이 없음
        if(end - start <= 10) {
            for(long i = start + 1 ; i <= end ; i ++) {
                result ^= i;    // xor계산
            }
        } else {
            for(long i = start + 1 ; i <= end ; i ++) {
                if(i % 4 == 0) break;
                result ^= i;
            }
            for(long i = end ; i >= start ; i --) {
                if(i % 4 == 3) break;
                result ^= i;
            }
        }

        System.out.println(result);
    }
}