大數運算實戰：計算不超過 n 位的最大 3 的冪次（C 語言數組模擬高精度）

大數運算實戰：計算不超過 n 位的最大 3 的冂（C 語言數組模擬高精度）

題目要求：給定 n (0 < n < 80)，輸出不超過 n 位的最大 3 的冂。直接用 int/long long 會在 n≥10 時溢出，必須實現高精度乘法。

高精度乘法核心思想

用整型數組 digit[] 存儲大整數，每個元素存一位（或四位），低位在低索引。乘以 3 時逐位相乘並處理進位。

完整算法步驟

1. 初始化 digit[0] = 1，長度 len = 1。
2. 循環 k = 1, 2, ...：
   • 對數組每位執行 digit[i] = digit[i] * 3 + carry，carry = digit[i] / 10，digit[i] %= 10。
   • 處理最高位進位，可能增加 len。
   • 若 len > n，跳出循環，上一輪結果即為答案。
3. 逆序輸出數組（高位在前）。

關鍵代碼實現

#include 
#include 

int main() {
    int n;
    scanf("%d", &n);
    int digit[200] = {0}; // 足夠存 80 位
    digit[0] = 1;
    int len = 1;
    int prev_len = 1;
    int prev_digit[200];

    for (int k = 1; ; k++) {
        // 備份上一輪結果
        prev_len = len;
        memcpy(prev_digit, digit, sizeof(digit));

        int carry = 0;
        for (int i = 0; i < len; i++) {
            int val = digit[i] * 3 + carry;
            digit[i] = val % 10;
            carry = val / 10;
        }
        while (carry > 0) {
            digit[len++] = carry % 10;
            carry /= 10;
        }
        if (len > n) break;
    }

    // 輸出上一輪結果
    for (int i = prev_len - 1; i >= 0; i--) {
        printf("%d", prev_digit[i]);
    }
    printf("\n");
    return 0;
}

複雜度分析

• 時間：O(n²) —— 外層循環約 n/ log10(3) 次，內層最多 n 次。
• 空間：O(n) —— 數組長度與 n 線性相關。

此方法通用於任意大整數乘法、冂運算，是 ACM/ICPC 入門必備技能。