模幂(模运算中的幂)

本文介绍了模幂(模运算中的幂)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

你好！ 我陷入了对模幂运算概念的了解.当我需要它以及它如何工作时. 假设我将幂函数调用为: power(2，n-1). n = 10

Hello! I am getting stuck in understanding the concept of modular Exponentiation. When i need this and how this works. Suppose i am calling the power function as : power(2,n-1). How the loops will be executed for say 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; }

推荐答案

从DAle链接的Wikipedia页面上的模定律(关于您的上一个问题)，我们可以获得两个公式:

From the modulo laws on DAle's linked Wikipedia page (on your previous question), we can obtain two formulas:

根据第一个公式，很明显，我们可以根据n / 2的结果迭代地计算n的模数.这是通过线条完成的

From the first formula it is clear that we can iteratively calculate the modulo for n from the result for n / 2. This is done by the lines

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

因此，算法中有log n个步骤，因为每次x的指数加倍.步数计数由n >>= 1和while (n > 0)完成，它们对log n步数进行计数.

There are thus log n steps in the algorithm, because each time the exponent of x doubles. The step counting is done by n >>= 1 and while (n > 0), which counts log n steps.

现在，您可能想知道1)为什么这部分没有设置res的值，以及2)这些行的目的是什么

Now, you may be wondering 1) why doesn't this part set the value of res, and 2) what is the purpose of these lines

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

这是必要的，因为在迭代的某些点，无论是开始还是结束，n的值都可能是奇数.我们不能只是忽略它，而是继续使用公式1，因为这意味着我们将跳过的力量为x！ (整数除法是四舍五入的，例如5 >> 1 = 2，我们将使用x^4而不是x^5).如果n为奇数(即n % 2 = n & 1 = 1)，则此if语句处理情况.它只是使用上面的公式2来将x的单次幂加"到结果中.

This is necessary as at certain points in the iteration, be it the start or the end, the value of n may be odd. We can't just ignore it and keep using formula 1, because that means we would skip a power of x! (Integer division rounds down, so e.g. 5 >> 1 = 2, and we would have x^4 instead of x^5). This if statement handles the case when n is odd, i.e. n % 2 = n & 1 = 1. It simply uses formula 2 above to "add" a single power of x to the result.