快速幂取模运算(Modular Exponentiation)

本文主要是介绍快速幂取模运算(Modular Exponentiation)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不考虑取模的快速幂运算（迭代法）

/* Iterative Function to calculate (x^y) in O(logy) */
int power(int x, unsigned int y)
{int res = 1;     // Initialize resultwhile (y > 0){// If y is odd, multiply x with resultif (y & 1)res = res*x;// n must be even nowy = y>>1; // y = y/2x = x*x;  // Change x to x^2}return res;
}

快速幂运算（取模）

/* Iterative Function to calculate (x^n)%p in O(logy) */
/*int可以换成long long 或者 unsigned long long*/
int power(int x, unsigned int y, int p)
{int res = 1;      // Initialize resultx = x % p;  // Update x if it is more than or // equal to pwhile (y > 0){// If y is odd, multiply x with resultif (y & 1)res = (res*x) % p;// y must be even nowy = y>>1; // y = y/2x = (x*x) % p;  }return res;
}

模运算的性质

这篇关于快速幂取模运算(Modular Exponentiation)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---