POJ 1220 進制轉換 Java 大數解法

題目大意

給定源進制 a、目標進制 b 及一個 a 進制數字串 c，要求將其轉換為 b 進制輸出。數值範圍極大，需用大整數處理。

Java 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 n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            String c = in.next();

            // 1. 將 a 進制字符串轉為十進制 BigInteger
            BigInteger sum = BigInteger.ZERO;
            for (int i = 0; i < c.length(); i++) {
                int digit = charToVal(c.charAt(i));
                sum = sum.multiply(BigInteger.valueOf(a)).add(BigInteger.valueOf(digit));
            }

            // 2. 將十進制轉為 b 進制字符串
            StringBuilder sb = new StringBuilder();
            if (sum.equals(BigInteger.ZERO)) {
                sb.append('0');
            } else {
                while (!sum.equals(BigInteger.ZERO)) {
                    int rem = sum.mod(BigInteger.valueOf(b)).intValue();
                    sb.append(valToChar(rem));
                    sum = sum.divide(BigInteger.valueOf(b));
                }
                sb.reverse();
            }

            System.out.println(a + " " + c);
            System.out.println(b + " " + sb.toString());
            System.out.println();
        }
    }

    static int charToVal(char ch) {
        if (ch >= '0' && ch <= '9') return ch - '0';
        if (ch >= 'A' && ch <= 'Z') return ch - 'A' + 10;
        return ch - 'a' + 36; // 支援至 62 進制
    }

    static char valToChar(int v) {
        if (v <= 9) return (char)('0' + v);
        if (v <= 35) return (char)('A' + v - 10);
        return (char)('a' + v - 36);
    }
}

核心思路

1. 利用 BigInteger 無限精度特性，避免溢出。
2. 字符到數值映射支援 0-9、A-Z、a-z 共 62 進制。
3. 轉換過程：源進制 → 十進制（BigInteger） → 目標進制字符串。

複雜度分析

• 時間：O(L * log_b(N))，L 為輸入長度，N 為數值大小。
• 空間：O(log_b(N)) 存儲結果字符串。