Ta có vài nhận xét sau:

• \(x \oplus x = 0\). (1)

• Nếu không bit \(1\) nào của \(x\) có cùng vị trí với bit \(1\) của \(y\) (2) thì \(x \oplus y = x + y\).

• Do \(M \leq 10^9\) nên bit có giá trị cao nhất có thể của \(M\) là \(30\) (Do \(2^{30} = 1073741824 > 10^9\)). (3)

• Nếu \(M | x\) và \(M | y\) (4) thì \(M | (x + y)\).

Không mất tính tổng quát, giả sử \(x \leq y \leq z\). Ta có \(x \oplus y \oplus z = 0 \Leftrightarrow x \oplus y = z\) (1). Nếu ta có thể tìm được \(x\) và \(y\) thỏa mãn (2) và (4) thì khi ta lấy \(z = x + y\) thì ta sẽ có \(1\) bộ ba \((x, y, z)\) thỏa mãn. Dựa vào \((3)\), ta có thể chọn \(x = M\) và \(y = M \times 2^{30}\).

Vậy \(1\) bộ ba có thể là \(x = M, y = M \times 2^{30}, z = M + M \times 2^{30}\).

Độ phức tạp: \(O(T)\)