大整數除法演算法詳解：PAT 1017 A除以B（20分）C語言實現

題目背景與挑戰

PAT（Basic Level）1017 A除以B 是經典的大整數除法題目。核心難點在於：被除數 A 最長可達 1000 位，遠超 long long（約 19 位）甚至 __int128 的表示範圍，必須採用字串模擬手算豎式除法的高精度演算法。

演算法核心邏輯：模擬手算豎式除法

回想小學數學豎式除法步驟：

1. 從最高位開始，取當前位與前一步餘數組成的數值作為「暫時被除數」
2. 暫時被除數 ÷ 除數 B = 當前商位，餘數留給下一位
3. 商位可能為 0，最高位的前導 0 需特殊處理（不輸出）
4. 最終餘數即為結果 R

數學公式化：

設 yu 為上一步餘數（初始 0），a[i] 為當前位字元對應的數值：

當前被除數 = yu * 10 + (a[i] - '0')
商位 = 當前被除數 / B
新餘數 = 當前被除數 % B

關鍵程式碼逐行解析

#include <stdio.h>
#include <string.h>

int main() {
    char a[1000];  // 儲存最多 1000 位的大整數字串
    int b;         // 除數（1 位正整數，1-9）
    int yu = 0;    // 餘數，初始為 0
    
    scanf("%s %d", a, &b);
    
    // 輸入合法性檢查：B 必須是 1-9，A 不能有前導 0（除非 A 本身是 0）
    if (b < 1 || b > 9 || a[0] == '0') return 0;
    
    int len = strlen(a);
    int started = 0;  // 標記是否已輸出非 0 商位（處理前導 0）
    
    for (int i = 0; i < len; i++) {
        int current = yu * 10 + (a[i] - '0');  // 當前被除數
        int quot = current / b;                // 當前商位
        yu = current % b;                      // 更新餘數
        
        // 處理前導 0：只有當商位非 0，或已經開始輸出，或是最後一位時才輸出
        if (quot != 0 || started || i == len - 1) {
            printf("%d", quot);
            started = 1;
        }
    }
    
    printf(" %d\n", yu);  // 輸出餘數
    return 0;
}

關鍵點詳細說明：

1. 字元轉數值：a[i] - '0' 利用 ASCII 碼順序將字元 '0'~'9' 轉為整數 0~9。
2. 前導 0 處理：變數 started 確保最高位的 0 不輸出；但若 A < B（如 3 ÷ 7），迴圈跑完 started 仍為 0，需在最後一位 i == len - 1 強制輸出一個 0。
3. 餘數更新：yu = current % b 精確模擬手算「帶下下一位」的過程。
4. 時間複雜度：O(N)，N 為 A 的位數（最多 1000），極其高效。

測試樣例驗證

輸入：123456789050987654321 7

逐步模擬前幾位：

• i=0: current=1, quot=0, yu=1 → 不輸出
• i=1: current=12, quot=1, yu=5 → 輸出 1
• i=2: current=53, quot=7, yu=4 → 輸出 7
• i=3: current=44, quot=6, yu=2 → 輸出 6
• ... 依此類推 ...

輸出：17636684150141093474 3 ✓ 與樣例完全一致。

常見錯誤與避坑指南

舉一反三：擴展應用

• 大整數加減乘除：同樣採用字串/陣列模擬手算，是高精度運算庫的基礎。
• 進制轉換：大整數十進制轉二進制/十六進制，核心同樣是重複除法取餘。
• 模冪運算：(a^b) % m 中 a 為大整數時，需結合快速冪與大整數模運算。

總結： PAT 1017 看似簡單，實則考察「字串處理」、「模擬演算法」、「邊界條件控制」三大核心能力。掌握豎式除法模擬邏輯，不僅能解決此題，更是攻克所有高精度運算問題的鑰匙。建議在紙上手算幾遍 12345 ÷ 7，再對照程式碼，方能悟透「帶下下一位」在程式中如何對應 yu * 10 + digit 這一關鍵行。