如何有效率計算大指數的(a^b)%MOD？

計算大指數的(a^b)%MOD

在本次程式設計挑戰中，任務是計算pow( a, b )%MOD，其中指數b 可能非常大。雖然傳統的 log(b) 時間複雜度方法適合較小的值，但當 b 超過 C 中 long long 資料類型的容量時，它就變得不切實際。

然而，更有效的方法涉及利用 Euler 的 totient 函數， φ(MOD)。歐拉定理指出 a^φ(MOD)≡1(mod MOD)。這意味著 a 的冪可以顯著降低為 a^(b % φ(MOD))。

計算 φ(MOD) 本身就是一項不平凡的任務，但可以使用整數分解法來實現。計算完成後，指數 b 可以替換為 b % φ(MOD)，以顯著減少計算時間。

進一步細化

2008 年，Schramm 證明φ (b) 可以透過gcd(b, i) 的離散傅立葉變換獲得，其中i 的範圍為1到b。這消除了顯式因式分解的需要。

此外，Carmichael 函數 λ(MOD) 可用於獲得正確答案，特別是當 a 和 MOD 共享公因數時。

程式碼實作

以下程式碼片段作為 C 語言的範例：

<code class="cpp">#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }

ll pmod(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b % 2 == 1) {
        return (a * pmod(a, b - 1, mod)) % mod;
    } else {
        ll tmp = pmod(a, b / 2, mod);
        return (tmp * tmp) % mod;
    }
}

int main() {
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout << pmod(a, b % phi(mod), mod) << endl;
    return 0;
}</code>

以上是如何有效率計算大指數的(a^b)%MOD？的詳細內容。更多資訊請關注PHP中文網其他相關文章！