c++ - 模幂(模算术中的幂)

Question

Hello!
I am got 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 and also the time and space complexity for the below problem

#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;

}

Answer 1

从 Dale 链接的维基百科页面上的模法则(关于您之前的问题)，我们可以获得两个公式:

从第一个公式可以清楚地看出，我们可以根据 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 的一次幂“添加”到结果中。