漢諾塔 C 語言大數取模：快速冪模算法 O(log n) 計算 (2^n - 1) % 9973

題目核心

漢諾塔最少步數 = `2^n - 1`。輸入 `n ≤ 10,000,000`，輸出對 `9973` 取模結果。
直接 `pow`/`<<` 會溢出，需**快速冪取模**。

快速冪模板

int mod_pow(int base, long long exp, int mod) {
    long long result = 1;
    long long b = base % mod;
    while (exp > 0) {
        if (exp & 1) result = (result * b) % mod;
        b = (b * b) % mod;
        exp >>= 1;
    }
    return (int)result;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n != 0) {
        if (n < 0) continue;
        int ans = (mod_pow(2, n, 9973) - 1 + 9973) % 9973; // 防負數
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點

• `mod_pow` 迭代 `O(log n)`，`n=10^7` 只需 ~24 次循環。
• 中間變量用 `long long` 防溢出（`9973^2 < 2^31`，`int` 其實也夠，但 `long long` 更保險）。
• 結果 `-1` 後加 `mod` 再取模，確保非負。
• 題目提示 `short` 也夠：`9973 < 32767`。