計算大指數的(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中文網其他相關文章!