[백준] 10464_XOR C++

30 Dec 2023 in Study on Coding Test

XOR 연산에 대해서 생각해보는 문제

정답제출코드

#include <iostream>
using namespace std;

int FindXOR(int n)
{
    int mod = n % 4;
 
    if (mod == 0) return n;
    else if (mod == 1) return 1;
    else if (mod == 2) return n + 1;
    else if (mod == 3) return 0;

    return 0;
}

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

    int T;
    cin >> T;

    for(int i = 0; i < T; ++i)
    {
        int s, f;
        cin >> s >> f;
    
        cout << (FindXOR(s - 1) ^ FindXOR(f)) << '\n';
    }
}

주어진 범위의 수 일일이 xor연산을 하면 시간초과가 발생할 것이라 생각했다.

그래서 규칙을 찾아보니

1부터 n까지 일일이 xor 연산을 진행하면

• n % 4 == 0일 때 n
• n % 4 == 1일 때 1
• n % 4 == 2일 때 n + 1
• n % 4 == 3일 때 0

의 규칙을 얻을 수 있다.

이를 이용해 1부터 S-1까지의 XOR을 구하고 1부터 F까지의 XOR을 구한 뒤

두 값을 다시 XOR하면 S부터 F까지의 XOR을 구할 수 있었다.