Lets say in a programming contest you need to find a^b % MOD .

One of the naive methods is to run a loop from 1 to b , keep multiplying and mod

```
prod = 1;
for(i=1;i<=b;i++)
{
prod*=a;
prod%=MOD;
}
```

This is done in order O(b) as it requires multiplying a b times
if b is as big as 10^6 or more it may give a **Time Limit Excedded** error

Lets look at it in an another way

Example You want to calculate 2^32 you can do divide and conquer

```
2^1 = 2
2^2 = (2^1)^2 = 4
2^4 = (2^2)^2 = 16
2^8 = (2^4)^2 = 256
2^16 = (2^8)^2 = 65536
2^32 = (2^16)^2 = 4294967296
```

Insted of 32 steps we found this in only 5 multiplication steps thus we can reduce a O(b) problem to an O( log(b) ) problem

Below is the code for Modular Integer exponentiaion in C++ for caluclating (a^p)%mod

```
#include<iostream>
using namespace std;
long long int exp(long long int a, long long int p ,long long int mod)
{
long long int result = 1;
long long int (p==0)
return 1;
long long int (p==1)
return a;
while(p)
{
if(p&1)
result *= a;
result%=mod;
p >>=1;
a*=a;
a%=mod;
}
return result;
}
int main()
{
long long int a,p,m;
m=1;
cout<<"Enter a , p and mod : ";
cin>>a>>p>>m;
cout<<exp(a,p,m)<<'\n';
return 0;
}
```

This can be extended to matrix also, insted of integer multiplication call a matrix multiplication (useful in Graph problems) Below is a C++ code for matrix multiplication

```
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define mod 1000000007
#define ull unsigned long long int
#define fl(i,n) for(i=0;i<n;i++)
#define pn printf('\n')
#define ps printf(' ')
using namespace std;
unsigned long long int** mmul(unsigned long long int** m,unsigned long long int** n,unsigned long long int N)
{
unsigned long long int i,j,k,**result;
result = new unsigned long long int* [N];
fl(i,N)
result[i]=new unsigned long long int[N];
fl(i,N)
fl(j,N)
{
result[i][j]=0;
fl(k,N)
result[i][j]+=m[i][k]*n[k][j];
}
return result;
}
unsigned long long int** mpow(unsigned long long int** matrix,unsigned long long int p,unsigned long long int n)
{
unsigned long long int **m,i,j;
m = new unsigned long long int* [n];
fl(i,n)
m[i]=new unsigned long long int[n];
fl(i,n)
fl(j,n)
{
if(i==j)
m[i][j]=1;
else
m[i][j]=0;
}
if(p==0)
return m;
else if(p==1)
return matrix;
while(p)
{
if(p&1)
m = mmul(m,matrix,n);
p>>=1;
matrix = mmul(matrix,matrix,n);
}
return m;
}
int main()
{
unsigned long long int n,i,j,p;
unsigned long long int** matrix;
cout<<"Enter N : ";
cin>>n;
matrix = new unsigned long long int* [n];
fl(i,n)
matrix[i]=new unsigned long long int[n];
cout<<"Enter Elements :\n";
fl(i,n)
fl(j,n)
cin>>matrix[i][j];
cout<<"Enter Power : ";
cin>>p;
matrix=mpow(matrix,p,n);
cout<<'\n';
fl(i,n)
{
fl(j,n)
cout<<matrix[i][j]<<' ';
cout<<'\n';
}
return 0;
}
```

Author

{"1eaa7f1": "/recommendation/pagelets/trending-card/?sensual=True"}

realtime.hackerearth.com

80

87ea2126ffcedec6d40a65e9bf51d1ef5d5fbe06

58a29e5cae2309f04b28

/realtime/pusher/auth/