XOR-Sum
Xem PDF
Đ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
6Output
0
7Note
- Nguồn: SPOJ
Bình luận
\(\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!
Dưới đây là bảng chân lý của phép toán XOR:
A (bit 1) B (bit 2) A XOR B
0 0 0
0 1 1
1 0 1
1 1 0
Trong Python, XOR là một phép toán logic được thực hiện bằng cách sử dụng toán tử ký hiệu ^. XOR (exclusive OR) hoạt động theo nguyên tắc sau:
Kết quả của phép toán XOR giữa hai bit là 1 nếu hai bit đó khác nhau.
Kết quả là 0 nếu hai bit đó giống nhau.
cho mình hỏi làm ⊕ nghĩa là sao vậy
nghĩa là sao vậy mọi người mình đọc hòi mà không hiểu