模塊求冪（模塊運算中的功率）

-6

您好！
我陷入了理解模數求冪的概念。當我需要這個和如何工作。
假設我正在調用電源功能：電源（2，n-1）。
如何環路將用於發言權N = 10模塊求冪（模塊運算中的功率）

#define m 1000000007 

unsigned long long int power(unsigned long long int x, unsigned long long int n){ 

    unsigned long long int res = 1; 
    while(n > 0){ 
     if(n & 1){ 
      res = res * x; 
      res = res % m; 
     } 
     x = x * x; 
     x= x % m; 
     n >>= 1; 
    } 
    return res; 

}

來源

2017-08-08 Himanshu Ray

你的問題「循環將如何執行說** n = 10 **」不清楚。難道你不能在紙上寫出步驟或使用調試器來查看在這種特殊情況下會發生什麼嗎？在任何情況下，** x **和** n **的值對於** m **生效的模數運算都太小，因此不是最好的示例。你是否想問一般該功能的工作原理和原因？ –

是@RoryDaulton。這個功能如何工作？ –

搜索「通過平方排列的指數」，它將解釋除'％m'行之外的所有內容，這些內容可以使所有模以'm'爲模。如果這些解釋中有什麼不明白的地方，那就回來再問一下詳情。 –

從戴爾的鏈接維基百科頁面上模法律的執行（在你前面的問題），我們可以得到兩個公式：

從第一個公式可知，我們可以從n/2的結果中迭代計算n的模。這是由線

x = x * x; 
x = x % m;

有這樣的算法log n步驟完成，因爲每次的x雙打指數。步數計數由n >>= 1和while (n > 0)完成，計數步數爲log n。

現在，你可能想知道1）爲什麼沒有這部分設置的res值，和2）什麼是這些線路的目的

if(n & 1){ 
    res = res * x; 
    res = res % m; 
}

這是必要的，因爲在某些點迭代，無論是開始還是結束，n的值可能都是奇數。我們不能忽略它，並繼續使用公式1，因爲這意味着我們將跳過一個x的力量！（整數部分舍入，例如5 >> 1 = 2，我們將有x^4而不是x^5）。此if語句處理n單數時的情況，即n % 2 = n & 1 = 1。它只是使用上面的公式2將x的單個功率「添加」到結果中。

來源

2017-08-08 11:41:19 meowgoesthedog

模塊求冪（模塊運算中的功率）

回答

相關問題