HDU 5047 Sawtooth 進階：高精度計算與 Java BigInteger 實現

題目回顧

同 HDU 5047，N 個「M」型圖形分割平面最大區域數公式為 \( 8N^2 - 7N + 1 \)。本文著重於 大數乘法 的多種實現策略。

C++ 分塊乘法詳解

將 \( M = 8N - 7 \) 拆為高低兩段，基數 \( B = 10^6 \) 或 \( 10^{12} \)：

• \( M = M_{\text{high}} \cdot B + M_{\text{low}} \)
• \( N \times M = N \times M_{\text{high}} \cdot B + N \times M_{\text{low}} \)
• 分別計算低段乘積並處理進位到高段
• 最後按高低段格式化輸出

代碼片段（基數 \( 10^6 \)）：

ll m = (n << 3) - 7;
ll high = m / MOD, low = m % MOD;
high *= n;
low = low * n + 1;
high += low / MOD;
low %= MOD;

Java BigInteger 版本

Java 內建 java.math.BigInteger 可直接處理任意大小整數，代碼極其簡潔：

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int cas = 1; cas <= T; cas++) {
            BigInteger n = in.nextBigInteger();
            BigInteger ans = n.multiply(n).multiply(BigInteger.valueOf(8))
                           .subtract(n.multiply(BigInteger.valueOf(7)))
                           .add(BigInteger.ONE);
            System.out.printf("Case #%d: %s\n", cas, ans);
        }
    }
}

輸入輸出優化

• C++：使用 scanf/printf，關閉同步流。
• Java：Scanner 配合 BufferedInputStream，輸出用 PrintWriter + BufferedOutputStream。

總結

同一數學模型，C++ 需手寫高精度乘法，Java 則憑藉 BigInteger 幾行搞定。實戰中視語言限制與時間限制選擇：若時限極緊（如 1s），C++ 手寫分塊乘法更快；若允許 Java 且時限寬鬆，BigInteger 開發效率極高。