BOJ 10464 - XOR / C++

문제 링크 : https://www.acmicpc.net/problem/10464

10464번: XOR

 

 

풀이

S와 F의 범위는 1부터 10억까지이므로 이를 직접 XOR하면 당연히 시간초과가 발생한다.

 

규칙을 찾기 위해 1부터 n까지의 XOR을 구해보면

n       이진수       1부터 n까지의 XOR
1         1           [0001]
2        10           [0011]
3        11           [0000]  <----- 0
4       100           [0100]  <----- n
5       101           [0001]
6       110           [0111]
7       111           [0000]  <----- 0
8      1000           [1000]  <----- n
9      1001           [0001]
10     1010           [1011]
11     1011           [0000] <------ 0
12     1100           [1100] <------ n

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을 구할 수 있다.

 

코드

#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(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

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

 

 

 

 

 

출처 : https://www.geeksforgeeks.org/calculate-xor-1-n/

https://www.geeksforgeeks.org/find-xor-of-numbers-from-the-range-l-r/​