ZeroJudge 解題筆記：r768.10622 - Perfect Pth Powers

作者：王一哲
日期：2026年9月8日


ZeroJudge 題目連結：r768.10622 - Perfect Pth Powers

解題想法

題目給一個整數 $x$，如果 $x = b^p$，找出最大的 $p$，如果 $x = 0$ 代表測資結尾，不需要計算。題目保證 $x$ 可以用 32-bit 的整數儲存。這題考質因數分解，假設 $x = 2^4 \times 3^2 = 144 = 12^2$，答案會被 $3^2$ 限制，答案為 $2$。先對 $x$ 質因數分解，找出所有質因數次方的最大公因數設為答案 $p$。用 while 迴圈從 $i = 2$ 開始測試，直到 $i^2 > x$ 為止，這個條件很重要，可以節省很多運算時間。如果跑完 while 迴圈之後 $x > 1$，代表 $x$ 是質數，答案 $p = 1$。

這題還有一個陷阱，當 $x < 0$ 時，$p$ 不能是偶數，這樣會使 $x$ 變為正值，必須將 $p$ 除以 $2$ 直到 $p$ 變成奇數為止。

Python 程式碼

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

from math import gcd

while True:
    x = int(input()) 
    if x == 0: break  # 結束
    if x == 1 or x == -1:  # 特例
        print(1)
        continue
        
    pm = 1  # 正負
    if x < 0:  # 處理負值
        pm = -1
        x = -x
    
    p = -1  # 答案先設為 -1
    i = 2  # 質因數從 2 開始往上找
    while x >= i * i:  # 重點，只要測試到 i = sqrt(x)
        m = 0  # 次方
        while x % i == 0:  # 不斷除以 i 找次方
            m += 1
            x //= i
        i += 1  # 因數加 1

        if m > 0:  # 次方大於 0
            if p == -1: p = m  # 第一個質因數，p 設定為 m
            else: p = gcd(p, m)  # 取 p, m 的最大公因數
    
    # 如果 x 大於 1，x 是質數，p 只能是 1
    if x > 1: p = 1
    
    # 如果 n 是負值，p 除以 2 直到 p 變為奇數
    if pm < 0:
        while p % 2 == 0:
            p //= 2
    # 印出答案
    print(p)

C ++程式碼

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

#include <cstdio>
#include <numeric>
using namespace std;

int main() {
    long x;
    while(scanf("%ld", &x) != EOF && x != 0) {
        if (x == 0) break;
        // 特例
        if (x == 1 || x == -1) {
            puts("1");
            continue;
        }

        // 處理負值
        int pm = 1;
        if (x < 0) {
            pm = -1;
            x = -x;
        }
        
        // 質因數分解
        long i = 2, p = -1;
        while(x >= i*i) {  // 如果用 int，i*i 可能會溢位
            long m = 0;
            while(x % i == 0) {
                m++;
                x /= i;
            }
            i++;
            
            // i 是質因數
            if (m > 0) {
                if (p == -1) p = m;
                else p = gcd(p, m);
            }
        }
        
        // x 是質數，p 只能是 1
        if (x > 1) p = 1;
        
        // x 是負值，p 必須是奇數
        if (pm < 0) {
            while(p % 2 == 0) {
                p /= 2;
            }
        }

        printf("%ld\n", p);
    }
}

C 語言程式碼

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

#include <stdio.h>

long gcd(long a, long b) {
    long r;
    while(b > 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

int main() {
    long x;
    while(scanf("%ld", &x) != EOF && x != 0) {
        // 特例
        if (x == 1 || x == -1) {
            puts("1");
            continue;
        }

        // 處理負值
        int pm = 1;
        if (x < 0) {
            pm = -1;
            x = -x;
        }
        
        // 質因數分解
        long i = 2, p = -1;
        while(x >= i*i) {
            long m = 0;
            while(x % i == 0) {
                m++;
                x /= i;
            }
            i++;
            
            // i 是質因數
            if (m > 0) {
                if (p == -1) p = m;
                else p = gcd(p, m);
            }
        }
        
        // x 是質數，p 只能是 1
        if (x > 1) p = 1;
        
        // x 是負值，p 必須是奇數
        if (pm < 0) {
            while(p % 2 == 0) {
                p /= 2;
            }
        }

        printf("%ld\n", p);
    }
}