ZeroJudge 解題筆記：c088. 00516 - Prime Land

作者：王一哲
日期：2026年2月24日


ZeroJudge 題目連結：c088. 00516 - Prime Land

解題想法

讀取一行測資，再每次讀取測資中的兩個數字，分別為底數及次方，將這個數字 $n$ 還原成 10 進位；接下來對 $n-1$ 做質因數分解，依照題目要求的格式輸出答案。

Python 程式碼

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

import sys

for line in sys.stdin:
    if line.rstrip() == "0": break
    arr = list(map(int, line.split()))  # 讀取一行資料
    n, m = 1, len(arr)  # n 儲存測資對應的整數，測資長度 m
    for i in range(0, m, 2):  # 一次讀取測資中的兩個數字
        n *= arr[i]**arr[i+1]  # 計算 n
    n -= 1  # 題目要算 n-1 的質因數分解結果
    curr = n  # 儲存 n-1，之後的計算會改變量值
    ans = []  # 答案
    for i in range(2, int(n**0.5)+1):  # 測試 2 ~ sqrt(n) 的質因數
        p = 0  # i 的次方
        while curr%i == 0:  # 如果 curr 能被 i 整除
            p += 1  # 次方加 1
            curr //= i  # curr 變為 1/i 倍
        if p > 0: ans += [p, i]  # 如果 p 大於 0，ans 加上 [p, i]
    if curr > 1: ans += [1, curr]  # 如果 curr 大於 1，ans 要加上 [1, curr]
    if not ans: print(n, 1)  # 如果 ans 是空的，n 是因數，輸出 n 1
    else: print(*ans[::-1])  # 題目要求因數由大到小輸出

C++ 程式碼

使用時間約為 2 ms，記憶體約為 408 kB，通過測試。

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cmath>
using namespace std;

int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    stringstream ss;
    while(getline(cin, s)) {
        if (s == "0") break;
        ss.clear(); ss << s;
        int n = 1, f, p;  // n 儲存測資對應的整數，因數 f、次方 p
        while(ss >> f >> p) {  // 一次讀取測資中的兩個數字
            for(int i=0; i<p; i++) n *= f;  // 計算 n
        }
        n --;  // 題目要算 n-1 的質因數分解結果
        int curr = n;  // 儲存 n-1，之後的計算會改變量值
        vector<int> ans;  // 答案
        for(int i=2; i<=(int)sqrt(n); i++) {  // 測試 2 ~ sqrt(n) 的質因數
            int cnt = 0;  // i 的次方
            while(curr%i == 0) {  // 如果 curr 能被 i 整除
                cnt++;  // 次方加 1
                curr /= i;  // curr 變為 1/i 倍
            }
            if (cnt > 0) {  // 如果 cnt 大於 0，ans 加上 [cnt, i]
                ans.push_back(cnt);
                ans.push_back(i);
            }
        }
        if (curr > 1) {  // 如果 curr 大於 1，ans 要加上 [1, curr]
            ans.push_back(1);
            ans.push_back(curr);
        }
        if (ans.empty()) {  // 如果 ans 是空的，n 是因數，輸出 n 1
            cout << n << " " << "1\n";
        } else {  // 題目要求因數由大到小輸出
            int alen = (int)ans.size();
            for(int i=alen-1; i>=0; i--) cout << ans[i] << " \n"[i == 0];
        }
    }
    return 0;
}