12
Exponentiation (Integer/Matrix) (Useful in Competitive Programming)
Competitive Programming
Competitive coding
Math

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