Phương trình

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Việc giải phương trình đại số Boolean với sự tham gia của các phép tính lô gic và xử lý bít khác khá xa với việc giải các phương trình đại số thông thường.

Để chứng minh cho điều đó, thầy giáo yêu cầu cả lớp về nhà xác định số lượng nghiệm không âm của từng phương trình trong số \(t\) phương trình, mỗi phương trình có dạng:

\(a-(a\oplus x)-x=0\)

trong đó:

  • \(x\) là ẩn số,
  • \(0 \le a < 2^{30}-1\),
  • \(\oplus\) là phép tính \(XOR\).

Input

  • Dòng đầu tiên chứa số nguyên \(t\ (1 \le t \le 1 000)\),
  • Mỗi dòng trong \(t\) dòng sau chứa số nguyên \(a (0 \le a < 2^{30})\).

Output

  • Đưa ra \(t\) số nguyên, mỗi số trên một dòng, số thứ \(i\) xác định số lượng nghiệm không âm của phương trình thứ \(i, i = 1 ÷ t\).

Example

Test 1

Input 
3 
0 
2
1073741823
Output 
1 
2
1073741824

Bình luận


  • 3
    jumptozero    6:28 p.m. 9 Tháng 6, 2021 ← chỉnh sửa 2

    Mình xin chia sẻ lời giải bài này như sau:

    • Đầu tiên, ta sẽ nhắc lại một số tính chất cơ bản của phép toán \(\oplus\) (hay còn gọi là phép XOR) như sau:

    • \(a \oplus 0 = a\)

    • \(a \oplus a = 0\)

    Lúc này, theo đề bài ta có: \(a-(a\oplus x)-x = 0 \iff a-x = a \oplus x \iff (a-x) \oplus x = a \implies (a-x) \oplus x = (a-x)+x\)

    Từ đây, quy về bài toán, tìm điều kiện của hai số không âm \(u,v\) bất kỳ thoả mãn \(u+v = u \oplus v\)

    Để giải quyết được vấn đề này, đầu tiên ta có một nhận xét như sau: \(u \oplus v \le u+v\) với mọi \(u,v\) không âm.

    Và điều này có thể được chứng minh như sau:

    • Đặt \(u=\overline{u_1u_2...u_n}_{(2)},v=\overline{v_1v_2...v_n}_{(2)}\) (trong đó \(u_i,v_i\in \left\{0,1\right\}\))

    Đến đây ta xét hai TH:

    • TH1: Giả sử tồn tại chỉ số \(k(1\le k\le n)\) nào đó thoả mãn: \(u_k=v_k=1\). Khi đó ta dễ dàng suy ra được \(u+v> u \oplus v\)
    • TH2: Không tồn tại chỉ số \(k(1\le k\le n)\) nào thoả mãn: \(u_k=v_k=1\). Khi đó ta có: \(u+v = u \oplus v\)

    Hay nói cách khác, để \(u+v=u \oplus v\). Thì \((u_i,v_i)\in \left\{(0,1),(1,0),(0,0)\right\}\)

    Lúc này, quay lại bài toán ban đầu: Ta cần tìm \(x\) sao cho \((a-x) \oplus x = a\)

    Đặt \((a-x)=\overline{p_1p_2...p_n}_{(2)},x=\overline{q_1q_2...q_n}_{(2)},a=\overline{a_1a_2...a_n}_{(2)}\)

    Khi đó \(a_i=1\) xảy ra khi và chỉ khi \((p_i,q_i)=(0,1)\) hoặc \((1,0)\) => Có \(2\) cách chọn để \(a_i=1\)

    Và \(a_i=0\) xảy ra khi và chỉ khi \((p_i,q_i)=(0,0)\) => Có \(1\) cách chọn để \(a_i=0\)

    Gọi \(e\) là số lượng số \(1\) trong biểu diễn nhị phân của số \(a\). Khi đó \(2^{e}\) chính là số nghiệm không âm của bài toán cần tìm

    Để tính được \(e\) có rất nhiều cách, nhưng ở đây, mình giới thiệu hàm \(\text{__builtin_popcount(a)}\) chính là hàm trả về số lượng số \(1\) của số \(a\) trong biểu diễn nhị phân.

    Như vậy là bài toán đã được giải quyết xong.

    Các bạn có thể tham khảo code mình tại đây: Link

    Ps: Nếu có gì khó hiểu hoặc sai sót, các bạn cứ comment nhé !


    • 0
      SPyofgame    9:12 p.m. 8 Tháng 6, 2021

      có phép XOR nào đâu ta

      1 phản hồi