Tổng và xor
Xem PDF
Điểm:
2400 (p)
Thời gian:
3.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn được cho 2 số \(n\) và \(k\). Nhiệm vụ của bạn là tìm 1 dãy số \(a\) nguyên dương độ dài \(x\) bất kỳ thỏa mãn:
- Các phần tử trong dãy \(a\) đôi một phân biệt
- \(a_1+a_2+\dots+a_x=n\)
- \(a_1\oplus a_2\oplus \dots\oplus a_x=k\)
Input
- Dòng đầu tiên nhập số \(t\) chỉ số trường hợp thử nghiệm
- Sau đó là \(t\) dòng, mỗi dòng nhập 2 số \(n\) và \(k\)
Output
- Với mỗi trường hợp có cách thỏa mãn:
- Dòng đầu tiên xuất ra số \(x\) là độ dài của dãy \(a\) thỏa mãn mà bạn tìm được
- Dòng tiếp theo xuất ra các phần tử trong dãy \(a\), các phần tử cách nhau bởi dấu cách. Bạn được quyền xuất ra bất cứ dãy nào thỏa mãn và theo bất cứ thứ tự nào.
- Với mỗi trường hợp không có cách thỏa mãn, xuất
IMPOSSIBLE
Constraints
- \(t\leq 10^5\)
- \(n,k\le 10^{18}\)
Scoring
- Subtask #1 (\(30\%\) số test): \(n\le 500\)
- Subtask #2 (\(70\%\) số test): Không có ràng buộc gì thêm
Example
Test 1
Input
5
1 1
3 2
12 0
36 18
49 25
Output
1
1
IMPOSSIBLE
3
2 4 6
4
4 5 7 20
3
8 20 9 12
Note
Lưu ý nhỏ: Ở trong ví dụ 3, ta không thể xuất dãy 2 4 6 0 vì có số 0 không phải số nguyên dương. Ta cũng không thể xuất dãy 6 6 vì dãy có 2 số 6 giống nhau
Bình luận