」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 如何有效率計算大指數的(a^b)%MOD?

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

發佈於2024-11-12
瀏覽:658

How to Efficiently Calculate (a^b)%MOD with Large Exponents?

使用大指數計算(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 共享公因數時。

程式碼實作
#include 
#include 

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 以下程式碼片段作為 C 語言的範例:

How to Efficiently Calculate (a^b)%MOD with Large Exponents?

#include #include 使用命名空間 std; typedef 長長 ll; ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); } ll pmod(ll a, ll b, ll mod) { 如果(b==0)返回1; 如果(b%2==1){ 返回 (a * pmod(a, b - 1, mod)) % mod; } 別的 { ll tmp = pmod(a, b / 2, mod); 返回 (tmp * tmp) % mod; } } int main() { ll a、b、mod; cin >> a >> b >> mod; cout
最新教學 更多>
  • Bootstrap 4 Beta 中的列偏移發生了什麼事?
    Bootstrap 4 Beta 中的列偏移發生了什麼事?
    Bootstrap 4 Beta:列偏移的刪除和恢復Bootstrap 4 在其Beta 1 版本中引入了重大更改柱子偏移了。然而,隨著 Beta 2 的後續發布,這些變化已經逆轉。 從 offset-md-* 到 ml-auto在 Bootstrap 4 Beta 1 中, offset-md-*...
    程式設計 發佈於2024-11-15
  • 如何在 C++ 巨集中模擬可選參數?
    如何在 C++ 巨集中模擬可選參數?
    C 中帶有可變參數的宏可選參數提供了一種指定具有預設值的參數的便捷方法,為函數呼叫提供了靈活性。雖然 C 本身不支援巨集中的可選參數,但有一些技術可以模擬這種行為。 一種方法涉及使用遞歸巨集模式。舉個例子:#define PRINT_STRING(message, ...) PRINT_STRING...
    程式設計 發佈於2024-11-15
  • JavaScript 中變數賦值左側的方括號有什麼作用?
    JavaScript 中變數賦值左側的方括號有什麼作用?
    解構賦值:揭示變數賦值左側方括號的意義在JavaScript 中,在變數賦值左側遇到方括號變數賦值的左側可能看起來令人困惑。為了破解這種語法的含義,我們冒險進入解構賦值的領域。 語法與操作解構賦值,這是JavaScript 1.7 和ECMAScript 6 中引入的功能,使我們能夠將陣列或物件中的...
    程式設計 發佈於2024-11-15
  • 將 MySQL 結果分組:SQL 與 PHP - 哪種方法最好?
    將 MySQL 結果分組:SQL 與 PHP - 哪種方法最好?
    MySQL 將結果依欄位資料分組:SQL 與PHP 方法在資料管理領域,可能會出現需要依欄位資料分組資料庫結果的情況,並以特定格式顯示它們。請考慮以下範例:範例1:根據群組ID 組織名稱清單:範例2:根據公用公用組ID 配對對應的標題和係數值:為了解決這些挑戰,出現了兩種主要方法:SQL 和PHP....
    程式設計 發佈於2024-11-15
  • 如何推遲載入大型 CSS 檔案以提高頁面效能?
    如何推遲載入大型 CSS 檔案以提高頁面效能?
    優化CSS交付:了解延遲CSS加載優化CSS交付時,在頁面加載後延遲加載大型CSS文件可以顯著提高頁面效能。雖然 Google 開發人員提供的範例演示​​了內聯小型 CSS 檔案以實現關鍵樣式,但它留下瞭如何推遲較大 CSS 檔案的問題。 加載後訪問原始CSS 文件要將大型CSS 文件的加載推遲到頁...
    程式設計 發佈於2024-11-15
  • 為什麼我注入的 CSS 在我的內容腳本中不起作用?
    為什麼我注入的 CSS 在我的內容腳本中不起作用?
    內容腳本中的CSS 注入問題疑難解答透過內容腳本將自訂CSS 注入網頁可能是擴展瀏覽器功能的有用技術。但是,如果注入的 CSS 不可見或不應用,則可能會令人沮喪。本文旨在解決可能出現此問題的原因並提供潛在的解決方案。 症狀:您已將內容腳本配置為注入 CSS 文件,但它確實如此不會出現在目標網頁上。 ...
    程式設計 發佈於2024-11-15
  • Javascript 基元其實是物件嗎?
    Javascript 基元其實是物件嗎?
    Javascript 基元與物件:澄清概念Javascript 基元與物件:澄清概念儘管普遍認為“Javascript 中幾乎所有內容都是物件”,但並非所有內容語言中的實體遵循這個定義。基元和物件之間的區別需要澄清。 基元與物件相反,基元是以其基本形式存在的不可變值。它們缺乏方法和屬性,並包含以下資...
    程式設計 發佈於2024-11-15
  • 為什麼 C++ 中的聯合內禁止使用 `std::string` 物件?
    為什麼 C++ 中的聯合內禁止使用 `std::string` 物件?
    為什麼std::string 在聯合中被禁止在C 程式設計領域,聯合是一種特殊的結構,它允許在聯合中儲存各種數據類型共享記憶體地址。然而,當涉及聯合中的成員時,有一個有趣的限制:禁止具有非平凡構造函數的類,包括 std::string。 非平凡構造函數的問題根本原因可以追溯到工會的性質。聯合體中的成...
    程式設計 發佈於2024-11-15
  • 我們能否在正規表示式中實現真正的可變長度向後尋找?
    我們能否在正規表示式中實現真正的可變長度向後尋找?
    正規表示式的可變長度回顧斷言替代方案正規表示式中的可變長度回顧斷言,用(?具有正規表示式模組的 PythonPython 正規表示式模組提供可變長度後向斷言的支援。 import regex m = regex.search('(?<!foo.*)bar', 'f00bar') pr...
    程式設計 發佈於2024-11-15
  • 您應該為您的應用程式選擇哪種地理鄰近度公式?
    您應該為您的應用程式選擇哪種地理鄰近度公式?
    地理位置鄰近度計算:公式比較在開發地理位置鄰近度搜尋時,了解公式選項之間的細微差別至關重要。雖然大圓距離公式和半正矢公式曾經被認為是同義詞,但它們之間存在一些微妙的區別,這些區別會影響速度、準確性和效率。 公式比較用於地理計算的三個主要公式鄰近度計算為:1。半正弦公式:d = 2r * arcsin...
    程式設計 發佈於2024-11-15
  • 如何在 PHP 中組合兩個關聯數組,同時保留唯一 ID 並處理重複名稱?
    如何在 PHP 中組合兩個關聯數組,同時保留唯一 ID 並處理重複名稱?
    在 PHP 中組合關聯數組在 PHP 中,將兩個關聯數組組合成一個數組是常見任務。考慮以下請求:問題描述:提供的代碼定義了兩個關聯數組,$array1和$array2。目標是建立一個新陣列 $array3,它合併兩個陣列中的所有鍵值對。 此外,提供的陣列具有唯一的 ID,而名稱可能重疊。要求是建構一...
    程式設計 發佈於2024-11-15
  • 如何使用 Twitter Bootstrap 對齊表格中的文字?
    如何使用 Twitter Bootstrap 對齊表格中的文字?
    Twitter Bootstrap 中的表格文字對齊在Twitter 的Bootstrap 架構中,您可以使用指定的文字對齊類別來對齊表格內的文本。 Bootstrap 3text-left:左對齊文字text-center:居中對齊文字text -right:右對齊文字Bootstrap 4te...
    程式設計 發佈於2024-11-15
  • 如何讓 CSS 中的空白表格儲存格的邊框可見?
    如何讓 CSS 中的空白表格儲存格的邊框可見?
    我可以在 CSS 中讓空白儲存格的邊框可見嗎? 在 Internet Explorer 7 中,預設可能不會顯示空白儲存格的邊框。不過,有幾種方法可以解決此問題。 使用不間斷空格如果可行,請插入不間斷空格 ( )進入空單元格可以強制瀏覽器渲染帶有邊框的單元格。 純 CSS解決方案對於純CSS解決方案...
    程式設計 發佈於2024-11-15
  • 如何將 Python 清單轉換為 CSV 檔案?
    如何將 Python 清單轉換為 CSV 檔案?
    將Python 清單清單匯出至CSV 檔案將Python 清單清單轉換為CSV 檔案,確保每個子清單中都會保留不同類型(浮點型、整數型、字串型)的資料。所需的 CSV 格式涉及使用逗號分隔每個子清單中的元素並垂直對齊子清單。 要實現此目的,您可以利用 Python 的內建 csv 模組:import...
    程式設計 發佈於2024-11-15
  • 測試限制:了解軟體測試的邊界
    測試限制:了解軟體測試的邊界
    软件测试是确保软件质量、稳定性和功能的开发过程的重要组成部分。然而,尽管测试很重要,但它也有其局限性。虽然它可以揭示缺陷,但它不能保证应用程序完全没有错误。了解这些限制有助于企业和开发人员设定切合实际的期望并优化他们的测试流程。在本文中,我们将探讨软件测试的主要局限性及其带来的挑战。 无法测试每个...
    程式設計 發佈於2024-11-15

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3