[zerojudge] c663: 正因數

題目連結：

c663: 正因數

題意：

給定某個大數的質因數分解表，

算出這個大數，

並且列出其全部的正因數。

解題策略：

運用遞迴的特性，

將其想成樹枝狀結構，

將每種組合都跑過一遍，

組成所有的正因數，

最後排序並輸出。

程式碼參考：

$Method \ 1.$：

對於每個質因數，

優先遞迴到底，

再向下一個質因數遞迴。

$PYTHON$：

$JUDGE\_RESULT$：$AC \ (1.1s, \ 26.3MB)$

from sys import stdin, stdout
def fn(cur, fac):
    if cur >= len(f): return # 已到最後的質因數了
    if f[cur][1]: # 如果指數大於 0
        ans.append(fac * f[cur][0])
        f[cur][1] -= 1 # 先減一次
        fn(cur, fac * f[cur][0]) # 遞迴
        f[cur][1] += 1 # 用完了要加回去
    fn(cur + 1, fac)
T = int(stdin.readline().strip())
for _ in range(T):
    data = stdin.readline().strip().split()
    f = []
    fac = 1
    for i in range(0, len(data), 2):
        f.append([int(data[i]), int(data[i + 1])])
        fac *= pow(int(data[i]), int(data[i + 1]))
    ans = [1]
    fn(0, 1)
    print(fac, ':', *sorted(ans))

$Method \ 2.$：

對於每個質因數，

都遞迴其指數的次數，

即可組和全部的因數。

$PYTHON$：

$JUDGE\_RESULT$：$AC \ (0.8s, \ 24.2MB)$

from sys import stdin
def fn(cur, fac):
    if cur >= len(f): return # 已到最後的質因數了
    tmp = 1
    for i in range(f[cur][1]):
        tmp *= f[cur][0] # 累積乘積
        ans.append(fac * tmp)
        fn(cur + 1, fac * tmp) # 遞迴
    fn(cur + 1, fac) # 往下一個遞迴
T = int(stdin.readline().strip())
for _ in range(T):
    data = stdin.readline().strip().split()
    f = [[int(data[i]), int(data[i + 1])] for i in range(0, len(data), 2)]
    mx = 0
    ans = [1]
    fn(0, 1)
    ans.sort()
    print(ans[-1], ':', *ans)

以上，

若有更好的想法歡迎提出哦！