XOR-Sum

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
dang7rickroll
Dạng bài
Ngôn ngữ cho phép
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Output, Pascal, Prolog, Python, Scala
Điểm: 900 Thời gian: 0.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Tính \(1 \oplus 2 \oplus 3 \oplus \dots \oplus n\) với \(n\) được nhập từ bàn phím.

Input

  • Dòng 1 chứa \(t\) \((t \leq 10^5)\) - số câu hỏi.
  • \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\).

Output

  • Ứng với mỗi câu hỏi in ra đáp án cần tìm.

Constraints

  • Subtask 1 [10%]: \(n \le 10\);
  • Subtask 2 [90%]: \(n \le 10^{12}\).

Example

Test 1

Input 
2
3
6
Output 
0
7

Note

  • Nguồn: SPOJ

Bình luận


  • -2
    hoangphucnguyen    9:41 a.m. 3 Tháng 9, 2024

    \(\color{red}{\text{Spoiler Alert}}\)

    \(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

    \(\color{red}{\text{Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.}}\)

    Khi bạn cần tính XOR của cả một dãy số như 1 ⊕ 2 ⊕ 3 ⊕ ... ⊕ n, có một quy luật mà bạn có thể dựa vào, giúp bạn không cần thực hiện từng bước một.

    Dưới đây là quy luật dựa vào kết quả của n % 4 (phần dư khi chia n cho 4):
    Nếu n % 4 == 0: Kết quả XOR của dãy số là n.
    Nếu n % 4 == 1: Kết quả XOR của dãy số là 1.
    Nếu n % 4 == 2: Kết quả XOR của dãy số là n + 1.
    Nếu n % 4 == 3: Kết quả XOR của dãy số là 0.

    Tại sao lại như vậy?
    Nếu bạn tính 1 ⊕ 2 ⊕ 3 ⊕ 4, bạn sẽ thấy rằng kết quả là 4. Nếu bạn thêm số tiếp theo (5), nó lại thay đổi, và tuần hoàn lặp lại sau mỗi 4 số.
    Do đó, bạn chỉ cần nhìn vào phần dư khi chia n cho 4 để biết kết quả XOR của cả dãy.

    Ví dụ:
    n = 7:
    7 % 4 = 3, vậy kết quả 1 ⊕ 2 ⊕ ... ⊕ 7 = 0.
    n = 5:
    5 % 4 = 1, vậy kết quả 1 ⊕ 2 ⊕ ... ⊕ 5 = 1.
    Hi vọng giải thích này giúp bạn hiểu rõ hơn về cách tính toán XOR!

      • 4 bình luận nữa