日期：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()
