模块求幂（模块运算中的功率）

-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

模块求幂（模块运算中的功率）

回答

相关问题