ZeroJudge 解題筆記：s562. 多項式 - 湊出 a_n

作者：王一哲
日期：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()

C++ 程式碼

理論上從 C++20 開始，可以引入函式庫 bit，呼叫 bit 之中的函式 popcount 計算一個整數的二進位制之中 1 的數量。但是 ZeroJudge 只有支援到 C++14，只能用 __builtin_popcount。解題時間約為 0.2 s，使用記憶體約為 1.6 MB。

#include <cstdio>

int main() {
    int t, n;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        scanf("%d", &n);
        printf("%d\n", __builtin_popcount(n));
    }
    return 0;
}

解題時間約為 0.2 s，使用記憶體約為 1.6 MB。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t, n;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cin >> n;
        cout << __builtin_popcount(n) << "\n";
    }
    return 0;
}

C 語言程式碼

解題時間約為 0.2 s，使用記憶體約為 1.5 MB。

#include <stdio.h>

int main() {
    int t, n;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        scanf("%d", &n);
        printf("%d\n", __builtin_popcount(n));
    }
    return 0;
}