Recent News

{
long long ans=1;
while(n>=1)
{
ans=(ans*n)%M;
n–;
}
return ans;
}Notice that on line 6, I performed the modulo operation at EACH intermediate stage.
It doesn’t make any difference if we first multiply all numbers and then modulo it by M, or we modulo at each stage of multiplication.( a * b * c ) % M is the same as ( ( ( a * b ) % M ) * c ) % MBut in case of computer programs, due to size of variable limitations we avoid the first approach andperform modulo M at each intermediate stageso that range overflow never occurs.So the following approach is wrong:long long factorial(int n,int M)//WRONG APPROACH!!!
{
long long ans=1;
while(n>=1)
{
ans=ans*n;
n–;
}
ans=ans%M;
return ans;
}The same procedure can be followed for addition too.( a + b + c ) % M is the same as ( ( ( a + b ) % M ) + c ) % MAgain we prefer the second way while writing programs. Perform % M every time a number is added so as to avoid overflow.The rules are a little different for division. This is the main part of this note;As I mentioned earlier,( a / b ) % c NOT EQUAL TO ( ( a % c ) / ( b % c ) ) % cwhich means that modulo operation is not distributive over division.The following concept is most important to find nCr (ways of selecting r objects from n objects) modulo M. (As an example, I’ve included the code to find nCr modulo M at the end of this note)To perform division in modulo arithmetic we need to first understand the concept ofmodulo multiplicative inverse.Lets go over some basics first.Themultiplicative inverseof a number y is z iff (z * y) == 1.Dividing a number x by another number y is same as multiplying x with the multiplicative inverse of y.x / y == x * y^(-1) == x * z (where z is multiplicative inverse of y)In normal arithmetic, the multiplicative inverse of y is y^(-1); which will correspond to some float value. Eg. Multiplicative inverse of 5 is 0.2, of 3 is 0.333… etc.But in modulo arithmetic the definition of multiplicative inverse of a number y is a little different.The modulo multiplicative inverse ( MMI ) of a number y is z iff (z * y) % M == 1.Eg. if M= 7 the MMI of 4 is 2 as ( 4 * 2 ) %7 ==1,if M=11, the MMI of 7 is 8 as ( 7 * 8 )%11 ==1,if M=13, the MMI of 7 is 2 as ( 7 * 2 ) % 13==1.Observe thatthe MMI of a number may be different for different M.So, if we are performing modulo arithmetic in our program and we need the result of the operation x / y, we should NOT performz=(x/y)%M;instead we should performy2=findMMI(y,M);
z=(x*y2)%M;Now one question remains.. How to find the MMI of a number n.The brute force approach would look something like thisint findMMI_bruteforce(int n,int M)
{
int i=1;
while(i<M)// we need to go only uptil M-1
{
if(( (long long)i * n ) % M ==1)
return i;
i++;
}
return -1;//MMI doesn’t exist
}The complexity of this approach is O(M) and as M is commonly equal to 10^9 + 7, this method is not efficient enough.There exist two other algorithms to find MMI of a number. First is theExtended Eucledian algorithmand the second usingFermat’s Little Theorem.If you are new to modulo arithmetic, you’ll probably not find these topics easy to understand.These algorithms require prerequisites. If you want to read them they are very well explained on many online sources and some of you will study them in depth in your college’s algorithm course too.I’ll keep this note simple for now and only give the code using Fermat Little Theorem.int fast_pow(long long base, long long n,long long M)
{
if(n==0)
return 1;
if(n==1)
return base;
long long halfn=fast_pow(base,n/2,M);
if(n%2==0)
return ( halfn * halfn ) % M;
else
return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
int findMMI_fermat(int n,int M)
{
return fast_pow(n,M-2,M);
}This code uses a function fast_pow() that is used to calculate the value of base^p. Its complexity is O(log p). It is a very efficient method of computing power of a number.It is based on the fact that to find a^n, we just need to find a^(n/2) and the required answer will bea^(n/2) * a^(n/2)if n is even; anda^((n-1)/2) * a^((n-1)/2) * aif n is odd ( if n is odd n/2 == (n-1)/2 in most programming languages ).NOTES:For M to be a prime number is really important. Because if it is not a prime number then it is possible that the result of a modulo operation may become 0. Eg. if M=12 and we perform ( 8 * 3 ) % 12, we’ll get 0. But if M is prime then ( ( a % M ) * ( b % M ) ) % M can never be 0 (unless a or b == 0)If M is prime then we can find MMI for any number n such that 1<=n<M( a – b ) % c = ( ( a % c ) – ( b % c ) ) %c is fine mathematically. But, while programming, don’t usea=(a%c);b=(b%c);ans=( a – b )%c;instead usea=a%c;b=b%c;ans = ( a – b + c ) % c;% works differently with -ve numbersIMPORTANT:1. If n1,n2 are int type variables and M=10^9+7, then the result of ( n1 * n2 ) % M will surely be < M ( and capable of fitting in a simple int variable). BUT the value of ( n1 * n2 ) can be greater than the capacity of an int variable. Internally, first ( n1 * n2 ) is computed. So, to avoid overflow either declare n or m as long long int OR use explicit type casting (( long long ) n * m ) % M.As an example, here is the code to find nCr modulo 1000000007, (0<=r<=n<=100000)int fast_pow(long long base, long long n,long long M)
{
if(n==0)
return 1;
if(n==1)
return base;
long long halfn=fast_pow(base,n/2,M);
if(n%2==0)
return ( halfn * halfn ) % M;
else
return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
int findMMI_fermat(int n,int M)
{
return fast_pow(n,M-2,M);
}
int main()
{
long long fact[100001];
fact[0]=1;
int i=1;
int MOD=1000000007;
while(i<=100000)
{
fact[i]=(fact[i-1]*i)%MOD;
i++;
}
while(1)
{
int n,r;
printf(“Enter n: “);
scanf(” %d”,&n);
printf(“Enter r: “);
scanf(” %d”,&r);
long long numerator,denominator,mmi_denominator,ans;
//I declared these variable as long long so that there is no need to use explicit typecasting
numerator=fact[n];
denominator=(fact[r]*fact[n-r])%MOD;
mmi_denominator=findMMI_fermat(denominator,MOD);
ans=(numerator*mmi_denominator)%MOD;
printf(“%lldn”,ans);
}
return 0;
}

News Reporter