日期：2026年8月8日
ZeroJudge 題目連結：s562. 多項式 - 湊出 a_n
解題想法
題目給一個函數定義 $$ \begin{align*} &~ (1 + qx)(1 + qx^2)(1 + qx^4)(1 + qx^8)(1 + qx^{16}) + \dots \\ &= a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \dots \end{align*} $$ 測資第一行為 $t$，代表接下來有 $t$ 行數字 $n$，要回傳 $a_n$ 對應的 $x$ 次方。實際上這題考的是二進位，$a_n$ 項的 $x$ 次方為 $n$ 的二進位制之中有幾個 $1$，例如 $a_6$ 為 $2 = 11_2$。
Python 程式碼
這題的記憶體限制很嚴格，只有 64 MB，而且測資數量極大。我一開始是用 for 迴圈及 input() 讀取資料，但是這樣會超時。後來改用 sys.stdin.read().split() 一次讀取所有測資，再用 sys.stdou.write() 輸出所有的答案，但是這樣寫會超出記憶體上限。最後是用 for 迴圈及 sys.stdin.readline() 讀取測資，計算完答案之後立刻用 sys.stdou.write() 輸出，才將時間壓在 0.5 s，記憶體壓在 8.5 MB。
超時。
t = int(input())
for _ in range(t):
n = int(input())
print(n.bit_count())
超出記憶體上限。
def solve():
import sys
result = []
data = sys.stdin.read().split()
ptr = 1
while ptr < len(data):
n = int(data[ptr])
ptr += 1
result.append(f"{n.bit_count()}\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
解題時間約為 0.5 s，使用記憶體約為 8.5 MB。
def solve():
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
sys.stdout.write(f"{n.bit_count()}\n")
if __name__ == "__main__":
solve()
