ZeroJudge 解題筆記：d131. 00160 - Factors and Factorials

作者：王一哲
日期：2026年4月17日


ZeroJudge 題目連結：d131. 00160 - Factors and Factorials

解題想法

題目要計算 $1!$ 到 $100!$ 每個數字之中，所有相乘的質數次方。可以先建 $1$ 到 $100$ 之間的質數表 $primes$。接下來用一個長度為 $101$ 的串列 $dp$，儲存 $1!$ 到 $100!$ 對應的答案，用字典格式儲存，key 為質數，value 為次方。由於 $i! = i \times (i-1)!$ ，更新 $dp[i]$ 時先複製 $dp[i-1]$ 的資料，再加上 $i$ 的質因數分解結果。最後再依序讀取測資，從 $dp$ 之中找對應的答案，排列成題目要求的格式並輸出。

Python 程式碼

使用時間約為 8 ms，記憶體約為 8.8 MB，通過測試。

def solve():
    import sys
    
    """ 1 ~ 100 之間的質數 """
    maxn = 100
    sieve = [True]*(maxn+1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(maxn**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, maxn+1, i):
                sieve[j] = False
    primes = [i for i in range(101) if sieve[i]]
    
    """ 建表，dp 的內容是 0 ~ 100 每個質因數對應的次方，字典格式 """
    dp = [{p:0 for p in primes} for _ in range(maxn+1)]
    for i in range(2, maxn+1):  # 依序測試 2 ~ 100
        dp[i] = dp[i-1].copy()  # 複製前一組的資料
        x = i  # 暫存 i 的值
        for p in primes:  # 依序讀取質數
            y = 0  # 要增加的次方
            while x%p == 0:  # 如果 p 可以整除 x
                y += 1  # y 加 1
                x //= p  # x 除以 p
            if y > 0:  # 如果 y 大於 0
                dp[i][p] += y  # 更新 dp[i][p] 對應的次方
            if x == 1: break  # 如果 x 等於 1，不需要再測試

    """ 讀取資料，從 dp 讀取質因數的次方，組合成答案 """
    result= []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break
        cofs = list(dp[n].values())  # 取出各個質因數的次方組成 list
        while cofs[-1] == 0: cofs.pop()  # 移除最後面的 0
        res = f"{n:3d}! ="  # 答案的開頭
        for i, cof in enumerate(cofs, start=1):  # 依序讀取 cofs
            res += f"{cof:3d}"  # 每個次方佔 3 格
            if i%15 == 0 and i < len(cofs): res += "\n      "  # 每 15 個要換行並空 6 格，如果是最後一項不換行
        res += "\n"  # 最後再換行
        result.append(res)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 1 ms，記憶體約為 3.3 MB，通過測試。

#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
using namespace std;

int main() {
    /* 1 ~ 100 之間的質數 */
    const int maxn = 100;
    vector<bool> sieve (maxn+1, true);
    sieve[0] = false;
    sieve[1] = false;
    for(int i=2; i<=(int)sqrt(maxn); i++) {
        if (sieve[i]) {
            for(int j=i*i; j<=maxn; j+=i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i=0; i<=maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }

    /* 建表，dp 的內容是 0 ~ 100 每個質因數對應的次方，字典格式 */
    vector<map<int, int>> dp (maxn+1);
    for(int p : primes) {
        dp[0][p] = 0;
        dp[1][p] = 0;
    }
    for(int i=2; i<=maxn; i++) {  // 依序測試 2 ~ 100
        dp[i] = dp[i-1];  // 複製前一組的資料
        int x = i;  // 暫存 i 的值
        for(int p : primes) {  // 依序讀取質數
            int y = 0;  // 要增加的次方
            while(x%p == 0) {  // 如果 p 可以整除 x
                y++;  // y 加 1
                x /= p;  // x 除以 p
            }
            if (y > 0) dp[i][p] += y;  // 如果 y 大於 0，更新 dp[i][p] 對應的次方
            if (x == 1) break;  // 如果 x 等於 1，不需要再測試
        }
    }
    /* 讀取資料，從 dp 讀取質因數的次方，組合成答案 */
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        vector<int> cofs;  // 取出各個質因數的次方組成 list
        for(auto it : dp[n]) cofs.push_back(it.second);
        while(cofs.back() == 0) cofs.pop_back();  // 移除最後面的 0
        printf("%3d! =", n);  // 答案的開頭
        int m = (int)cofs.size();  // 係數的數量
        for(int i=0; i<m; i++) {  // 依序讀取 cofs
            printf("%3d", cofs[i]);  // 每個次方佔 3 格
            if ((i+1)%15 == 0 && i+1 < m) printf("\n      ");  // 每 15 個要換行並空 6 格，如果是最後一項不換行
        }
        printf("\n");  // 最後再換行
    }
    return 0;
}