POJ 1001 Exponentiation：大數冪次運算解題詳解

題目概述

給定一個浮點數 a 與整數 b，求 a^b。輸入包含多組測資，需處理前導零、尾部零及科學記號輸出問題。a 可能包含小數點，b 為非負整數。

核心思路

使用 Java BigDecimal 進行高精度運算：

1. 讀入 BigDecimal a 與 int b。
2. 呼叫 a.pow(b) 計算冪次。
3. 以 toPlainString() 取得不含科學記號的完整字串。
4. 移除前導零（保留小數點前至少一位）與尾部零（若小數點後全為零則連同小數點一併移除）。

關鍵細節

• 科學記號：toString() 可能輸出 1.23E+10，必須用 toPlainString()。
• 前導零處理：從索引 0 開始跳過 '0'，但若遇到小數點則停止，確保 0.123 不會變成 .123。
• 尾部零處理：從字串末端往前跳過 '0'，若最終停在小數點，則再退一格移除小數點。

完整 Java 代碼

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            BigDecimal a = cin.nextBigDecimal();
            int b = cin.nextInt();
            a = a.pow(b);
            String s = a.toPlainString(); // 避免科學記號

            int start = 0;
            while (start < s.length() && s.charAt(start) == '0') start++;
            int end = s.length() - 1;
            while (end >= 0 && s.charAt(end) == '0') end--;
            if (end >= 0 && s.charAt(end) == '.') end--; // 去掉小數點

            if (start > end) { // 結果為 0
                System.out.println("0");
            } else {
                for (int i = start; i <= end; ++i) System.out.print(s.charAt(i));
                System.out.println();
            }
        }
        cin.close();
    }
}

複雜度分析

BigDecimal.pow 內部採用快速冪演算法，時間複雜度約 O(M(log b))，M 為大數乘法複雜度。字串處理為線性時間。空間複雜度取決於結果位數。

常見坑點

• 輸入結束條件：while(cin.hasNext()) 處理多組測資。
• b = 0 時結果為 1，需正確輸出。
• 純小數如 0.001 經冪次後可能產生大量前導零，迴圈條件需嚴謹。