[Geeks for Geeks] Modular Exponentiation for large numbers

Modular Exponentiation for large numbers

Implement pow(x, n) % M.

In other words, given x, n and M, find (xn) % M.

  • Time : O(logn)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution
{
public:
long long int PowMod(long long int x,long long int n,long long int M)
{
if(n == 1) return x % M;
long long int res = PowMod(x, n>>1, M);
res = (res * res) % M;
if(n & 1) res = (res * x) % M;
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/GeeksforGeeks/modular-exponentiation-for-large-numbers/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.