C 語言實現大數冪運算取模：快速冪算法詳解

題目要求

計算 x^y mod 1,000,000,007，其中 2 ≤ x, y ≤ 10^9，多組測試數據，暴力乘法會超時。

核心算法：二進制快速冪

利用指數的二進制分解：y = 2^a + 2^b + ...，則 x^y = x^(2^a) * x^(2^b) * ...。預先通過平方快速得到 x^(2^i)，再按二進制位相乘，時間複雜度 O(log y)。

關鍵代碼框架

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

注意使用 64 位整型防止中間乘積溢出，或採用 __int128 / 模乘函數。