fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. // - Đặt f(a, b) = Tổng xor từ a đến b = a ^ (a + 1) ^ (a + 2) ^ ... ^ (b - 1) ^ b
  12. // => f(a, b) = f(0, b) ^ f(0, a - 1)
  13. // => Bài toán đưa về chỉ cần quan tâm đến f(0, n) = Tổng xor từ 0 đến n = 0 ^ 1 ^ 2 ^ ... ^ (n - 1) ^ n
  14. // - Để tính f(0, n) thì ta có nhiều cách như dp digit hay math
  15. // - Ngoài ra còn có cách đơn giản hơn nhưng phải ra được nhận xét sau:
  16. // "Tổng xor của 4 số liên tiếp có dạng 4k, 4k + 1, 4k + 2, 4k + 3 (k >= 0) bằng 0"
  17.  
  18. // ll f(ll n) {
  19. // int len = (n + 1) % 4;
  20. // ll ans = 0;
  21. // for (ll i = n - len + 1; i <= n; i++) {
  22. // ans ^= i;
  23. // }
  24. // return ans;
  25. // }
  26.  
  27. ll f(ll n) {
  28. if (n % 4 == 0) return n;
  29. if (n % 4 == 1) return 1;
  30. if (n % 4 == 2) return n + 1;
  31. return 0;
  32. }
  33.  
  34. int main() {
  35. ios::sync_with_stdio(false);
  36. cin.tie(nullptr);
  37. ll a, b;
  38. cin >> a >> b;
  39. ll ans = f(b) ^ f(a - 1);
  40. cout << ans << '\n';
  41. }
Success #stdin #stdout 0.01s 5312KB
stdin
2 4
stdout
5