【題解】AtCoder ABC 121D – XOR World

【題目敘述】https://atcoder.jp/contests/abc121/tasks/abc121_d
【解題想法】

• f (a, b): 數字 a ~ b 的 XOR 結果
• 觀察數字XOR的結果，發現有每四個一組的規律：
  • 0：0000, f(0, 0) = 0 (0 % 4 = 0)
  • 1：0001, f(0, 1) = 1 (0 % 4 = 1)
  • 2：0010, f(0, 2) = 3 (0 % 4 = 2)
  • 3：0011, f(0, 3) = 0 (0 % 4 = 3)
  • ————————————
  • 4：0100, f(0, 4) = 4 (0 % 4 = 0)
  • 5：0101, f(0, 5) = 1 (0 % 4 = 1)
  • 6：0110, f(0, 6) = 7 (0 % 4 = 2)
  • 7：0111, f(0, 7) = 0 (0 % 4 = 3)
  • ————————————
• 歸納：
  • if n % 4 = 0, f (0, n) = n,
  • if n % 4 = 1, f (0, n) = 1
  • if n % 4 = 2, f (0, n) = n+1
  • if n % 4 = 3, f (0, n) = 0
• f (a, b) = f (a-1) ^ f (b)

#include <bits/stdc++.h>
using namespace std;
 
long long a, b;
 
int main(){
    cin >> a >> b;
    if (b % 4 == 1) b = 1;
    else if (b % 4 == 2) b++;
    else if (b % 4 == 3) b = 0;
    if (a == 0){
        cout << b << "\n";
        return 0;
    }
    a--;
    if (a % 4 == 1) a = 1;
    else if (a % 4 == 2) a++;
    else if (a % 4 == 3) a = 0;
    cout << (b ^ a) << "\n";
}