Để giải bài này, hãy thử đổi góc nhìn một chút.

Giả sử tập \(P\) gồm mọi lũy thừa của \(2\). Khi đó tập \(S\) sẽ là tập số nguyên dương \(\mathbb{Z}^+\).

Xét bài toán tổng quát, tập \(P\) gồm mọi lũy thừa của \(p \ge 2\).
Ta coi mỗi cách chọn một vài số trong tập \(P\) như một số nhị phân \(r\) : chọn số \(p^i\) tương ứng với bit thứ \(i\) trong \(r\) được bật (\(r = r + 2^i\)).

Vì ta chỉ chọn các số \(p^i\) phân biệt, nên tập các số \(r\) có thể tạo ra chính là \(\mathbb{Z}^+\). Nhằm thuận tiện, ta kí hiệu \(f(r)\) là số tương ứng trong tập \(S\) tạo bởi 'cách chọn' \(r\).

Tính chất : $1 \le a < b \Leftrightarrow f(a) < f(b) $

• Chiều thuận : \(a < b\) nên khi xét biểu diễn nhị phân của hai số, tồn tại duy nhất một vị trí \(i\) mà phần tiền tố trước bit \(i\) của \(a,b\) giống nhau, mà \(a[i] < b[i]\).

Theo công thức cấp số cộng : $\(\sum_{k=0}^{i-1}p^k = \frac{p^i - 1}{p - 1} < p^i\)$ nên \(f(a) < f(b)\)

• Chiều nghịch : Chứng minh phản chứng. Giả sử từ \(f(a) < f(b)\), suy ra được \(a > b\) (hiển nhiên \(a \ne b\) vì \(f(a) \ne f(b)\)).

Lúc này ta lấy được một số \(c\) mà \(b \le c < a\). Như đã chứng minh ở trên, ta có được \(f(b) \le f(c) < f(a)\)

Không thể vừa có \(f(a) < f(b)\) vừa có \(f(b) < f(a)\) nên điều đã giả sử là sai. Suy ra ĐPCM.

Kết luận : Mỗi cách chọn một vài lũy thừa \(p^j\) trong tập \(P\) cho ra một số phân biệt trong tập \(S\).

Số lớn thứ \(i\) : \(1 \le i\) trong tập \(S\) bằng \(\sum p^j\), với \(i = \sum 2^j\) (\(j\) là những bit được bật trong biểu diễn nhị phân của \(i\)) \(( * )\)

Về mặt cài đặt của bài này, cần xử lý số lớn (BigNum), và lưu trước vào mảng luỹ_thừa[x] = 3^x để không phải tính lại tại mỗi truy vấn.