COME ON CODE ON

A blog about programming and more programming.

Posts Tagged ‘Euler

Modular Multiplicative Inverse

with 33 comments

The modular multiplicative inverse of an integer a modulo m is an integer x such that a^{-1} \equiv x \pmod{m}.

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to ax \equiv aa^{-1} \equiv 1 \pmod{m}.

The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1).

Let’s see various ways to calculate Modular Multiplicative Inverse:

1. Brute Force
We can calculate the inverse using a brute force approach where we multiply a with all possible values x and find a x such that ax \equiv 1 \pmod{m}. Here’s a sample C++ code:

int modInverse(int a, int m) {
	a %= m;
	for(int x = 1; x < m; x++) {
		if((a*x) % m == 1) return x;
	}
}

The time complexity of the above codes is O(m).

2. Using Extended Euclidean Algorithm
We have to find a number x such that a·x = 1 (mod m). This can be written as well as a·x = 1 + m·y, which rearranges into a·x – m·y = 1. Since x and y need not be positive, we can write it as well in the standard form, a·x + m·y = 1.

In number theory, Bézout’s identity for two integers a, b is an expression ax + by = d, where x and y are integers (called Bézout coefficients for (a,b)), such that d is a common divisor of a and b. If d is the greatest common divisor of a and b then Bézout’s identity ax + by = gcd(a,b) can be solved using Extended Euclidean Algorithm.

The Extended Euclidean Algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y (one of which is typically negative) that satisfy Bézout’s identity
ax + by = gcd(a,b). The Extended Euclidean Algorithm is particularly useful when a and b are coprime, since x is the multiplicative inverse of a modulo b, and y is the multiplicative inverse of b modulo a.

We will look at two ways to find the result of Extended Euclidean Algorithm.

Iterative Method
This method computes expressions of the form ri = axi + byi for the remainder in each step i of the Euclidean algorithm. Each successive number ri can be written as the remainder of the division of the previous two such numbers, which remainder can be expressed using the whole quotient qi of that division as follows:
r_i = r_{i-2} - q_i r_{i-1}.\,
By substitution, this gives:
r_i = (ax_{i-2} + by_{i-2}) - q_i (ax_{i-1} + by_{i-1}),\,which can be written
r_i = a(x_{i-2} - q_i x_{i-1}) + b(y_{i-2} - q_i y_{i-1}).\,
The first two values are the initial arguments to the algorithm:
r_1 = a = a\times1 + b\times0\,
r_2 = b = a\times0 + b\times1.\,
So the coefficients start out as x1 = 1, y1 = 0, x2 = 0, and y2 = 1, and the others are given by
x_i = x_{i-2} - q_i x_{i-1},\,
y_i = y_{i-2} - q_i y_{i-1}.\,
The expression for the last non-zero remainder gives the desired results since this method computes every remainder in terms of a and b, as desired.

So the algorithm looks like,

  1. Apply Euclidean algorithm, and let qn(n starts from 1) be a finite list of quotients in the division.
  2. Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
    1. Then for each i so long as qi is defined,
    2. Compute xi+1 = xi-1qixi
    3. Compute yi+1 = yi-1qiyi
    4. Repeat the above after incrementing i by 1.
  3. The answers are the second-to-last of xn and yn.
/* This function return the gcd of a and b followed by
	the pair x and y of equation ax + by = gcd(a,b)*/
pair<int, pair<int, int> > extendedEuclid(int a, int b) {
	int x = 1, y = 0;
	int xLast = 0, yLast = 1;
	int q, r, m, n;
	while(a != 0) {
		q = b / a;
		r = b % a;
		m = xLast - q * x;
		n = yLast - q * y;
		xLast = x, yLast = y;
		x = m, y = n;
		b = a, a = r;
	}
	return make_pair(b, make_pair(xLast, yLast));
}

int modInverse(int a, int m) {
    return (extendedEuclid(a,m).second.first + m) % m;
}

Recursive Method
This method attempts to solve the original equation directly, by reducing the dividend and divisor gradually, from the first line to the last line, which can then be substituted with trivial value and work backward to obtain the solution.
Notice that the equation remains unchanged after decomposing the original dividend in terms of the divisor plus a remainder, and then regrouping terms. So the algorithm looks like this:

  1. If b = 0, the algorithm ends, returning the solution x = 1, y = 0.
  2. Otherwise:
    • Determine the quotient q and remainder r of dividing a by b using the integer division algorithm.
    • Then recursively find coefficients s, t such that bs + rt divides both b and r.
    • Finally the algorithm returns the solution x = t, and y = s − qt.

Here’s a C++ implementation:

/* This function return the gcd of a and b followed by
	the pair x and y of equation ax + by = gcd(a,b)*/
pair<int, pair<int, int> > extendedEuclid(int a, int b) {
	if(a == 0) return make_pair(b, make_pair(0, 1));
	pair<int, pair<int, int> > p;
	p = extendedEuclid(b % a, a);
	return make_pair(p.first, make_pair(p.second.second - p.second.first*(b/a), p.second.first));
}

int modInverse(int a, int m) {
    return (extendedEuclid(a,m).second.first + m) % m;
}

The time complexity of the above codes is O(log(m)2).

3. Using Fermat’s Little Theorem
Fermat’s little theorem states that if m is a prime and a is an integer co-prime to m, then ap − 1 will be evenly divisible by m. That is a^{m-1} \equiv 1 \pmod{m}. or a^{m-2} \equiv a^{-1} \pmod{m}. Here’s a sample C++ code:

/* This function calculates (a^b)%MOD */
int pow(int a, int b, int MOD) {
int x = 1, y = a;
	while(b > 0) {
		if(b%2 == 1) {
			x=(x*y);
			if(x>MOD) x%=MOD;
		}
		y = (y*y);
		if(y>MOD) y%=MOD;
		b /= 2;
	}
	return x;
}

int modInverse(int a, int m) {
    return pow(a,m-2,m);
}

The time complexity of the above codes is O(log(m)).

4. Using Euler’s Theorem
Fermat’s Little theorem can only be used if m is a prime. If m is not a prime we can use Euler’s Theorem, which is a generalization of Fermat’s Little theorem. According to Euler’s theorem, if a is coprime to m, that is, gcd(a, m) = 1, then a^{\varphi(m)} \equiv 1 \pmod{m}, where where φ(m) is Euler Totient Function. Therefore the modular multiplicative inverse can be found directly: a^{\varphi(m)-1} \equiv a^{-1} \pmod{m}. The problem here is finding φ(m). If we know φ(m), then it is very similar to above method.


Now lets take a little different question. Now suppose you have to calculate the inverse of first n numbers. From above the best we can do is O(n log(m)). Can we do any better? Yes.

We can use sieve to find a factor of composite numbers less than n. So for composite numbers inverse(i) = (inverse(i/factor(i)) * inverse(factor(i))) % m, and we can use either Extended Euclidean Algorithm or Fermat’s Theorem to find inverse for prime numbers. But we can still do better.

a * (m / a) + m % a = m
(a * (m / a) + m % a) mod m = m mod m, or
(a * (m / a) + m % a) mod m = 0, or
(- (m % a)) mod m = (a * (m / a)) mod m.
Dividing both sides by (a * (m % a)), we get
– inverse(a) mod m = ((m/a) * inverse(m % a)) mod m
inverse(a) mod m = (- (m/a) * inverse(m % a)) mod m

Here’s a sample C++ code:

vector<int> inverseArray(int n, int m) {
	vector<int> modInverse(n + 1,0);
	modInverse[1] = 1;
	for(int i = 2; i <= n; i++) {
		modInverse[i] = (-(m/i) * modInverse[m % i]) % m + m;
	}
	return modInverse;
}

The time complexity of the above code is O(n).

-fR0DDY

Written by fR0DDY

October 9, 2011 at 12:29 AM

Combination

with 15 comments

In mathematics a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter. More formally a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements the number of k-combinations is equal to the binomial coefficient. In this post we will see different methods to calculate the binomial.

1. Using Factorials
We can calculate nCr directly using the factorials.
nCr = n! / (r! * (n-r)!)

#include<iostream>
using namespace std;

long long C(int n, int r)
{
    long long f[n + 1];
    f[0]=1;
    for (int i=1;i<=n;i++)
        f[i]=i*f[i-1];
    return f[n]/f[r]/f[n-r];
}

int main()
{
	int n,r,m;
	while (~scanf("%d%d",&n,&r))
	{
		printf("%lld\n",C(n, min(r,n-r)));
	}
}

But this will work for only factorial below 20 in C++. For larger factorials you can either write big factorial library or use a language like Python. The time complexity is O(n).
If we have to calcuate nCr mod p(where p is a prime), we can calculate factorial mod p and then use modular inverse to find nCr mod p. If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then use Chinese Remainder Theorem(CRT) to find nCr mod m.

#include<iostream>
using namespace std;
#include<vector>

/* This function calculates (a^b)%MOD */
long long pow(int a, int b, int MOD)
{
	long long x=1,y=a; 
	while(b > 0)
	{
		if(b%2 == 1)
		{
			x=(x*y);
			if(x>MOD) x%=MOD;
		}
		y = (y*y);
		if(y>MOD) y%=MOD; 
		b /= 2;
	}
	return x;
}

/* 	Modular Multiplicative Inverse
	Using Euler's Theorem
	a^(phi(m)) = 1 (mod m)
	a^(-1) = a^(m-2) (mod m) */
long long InverseEuler(int n, int MOD)
{
	return pow(n,MOD-2,MOD);
}

long long C(int n, int r, int MOD)
{
	vector<long long> f(n + 1,1);
	for (int i=2; i<=n;i++)
		f[i]= (f[i-1]*i) % MOD;
	return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}

int main()
{    
	int n,r,p;
	while (~scanf("%d%d%d",&n,&r,&p))
	{
		printf("%lld\n",C(n,r,p));
	}
}

2. Using Recurrence Relation for nCr
The recurrence relation for nCr is C(i,k) = C(i-1,k-1) + C(i-1,k). Thus we can calculate nCr in time complexity O(n*r) and space complexity O(n*r).

#include<iostream>
using namespace std;
#include<vector>

/*
	C(n,r) mod m
	Using recurrence:
	C(i,k) = C(i-1,k-1) + C(i-1,k)
	Time Complexity: O(n*r)
	Space Complexity: O(n*r)
*/

long long C(int n, int r, int MOD)
{
	vector< vector<long long> > C(n+1,vector<long long> (r+1,0));

	for (int i=0; i<=n; i++)
	{
		for (int k=0; k<=r && k<=i; k++)
			if (k==0 || k==i)
				C[i][k] = 1;
			else
				C[i][k] = (C[i-1][k-1] + C[i-1][k])%MOD;
	}
	return C[n][r];
}
int main()
{
	int n,r,m;
	while (~scanf("%d%d%d",&n,&r,&m))
	{
		printf("%lld\n",C(n, r, m));
	}
}

We can easily reduce the space complexity of the above solution by just keeping track of the previous row as we don’t need the rest rows.

#include<iostream>
using namespace std;
#include<vector>

/*
	Time Complexity: O(n*r)
	Space Complexity: O(r)
*/
long long C(int n, int r, int MOD)
{
	vector< vector<long long> > C(2,vector<long long> (r+1,0));

	for (int i=0; i<=n; i++)
	{
		for (int k=0; k<=r && k<=i; k++)
			if (k==0 || k==i)
				C[i&1][k] = 1;
			else
				C[i&1][k] = (C[(i-1)&1][k-1] + C[(i-1)&1][k])%MOD;
	}
	return C[n&1][r];
}

int main()
{
	int n,r,m,i,k;
	while (~scanf("%d%d%d",&n,&r,&m))
	{
		printf("%lld\n",C(n, r, m));
	}
}

3. Using expansion of nCr
Since

C(n,k) = n!/((n-k)!k!)
         [n(n-1)...(n-k+1)][(n-k)...(1)]
       = -------------------------------
           [(n-k)...(1)][k(k-1)...(1)]


We can cancel the terms: [(n-k)…(1)] as they appear both on top and bottom, leaving:

    n (n-1)     (n-k+1)
    - ----- ... -------
    k (k-1)       (1)

which we might write as:

C(n,k) = 1,                 if k = 0
       = (n/k)*C(n-1, k-1), otherwise

#include<iostream>
using namespace std;

long long C(int n, int r)
{
	if (r==0) return 1;
    else return C(n-1,r-1) * n / r;
}

int main()
{
	int n,r,m;
	while (~scanf("%d%d",&n,&r))
	{
		printf("%lld\n",C(n, min(r,n-r)));
	}
}

4. Using Matrix Multiplication
In the last post we learned how to use Fast Matrix Multiplication to calculate functions having linear equations in logarithmic time. Here we have the recurrence relation C(i,k) = C(i-1,k-1) + C(i-1,k).
If we take k=3 we can write,
C(i-1,1) + C(i-1,0) = C(i,1)
C(i-1,2) + C(i-1,1) = C(i,2)
C(i-1,3) + C(i-1,2) = C(i,3)
Now on the left side we have four variables C(i-1,0), C(i-1,1), C(i-1,2) and C(i-1,3).
On the right side we have three variables C(i,1), C(i,2) and C(i,3).
We need those two sets to be the same, except that the right side index numbers should be one higher than the left side index numbers. So we add C(i,0) on the right side. NOw let’s get our all important Matrix.

(.   .   .   .)  ( C(i-1,0) )   ( C(i,0) )
(.   .   .   .)  ( C(i-1,1) ) = ( C(i,1) )
(.   .   .   .)  ( C(i-1,2) )   ( C(i,2) )
(.   .   .   .)  ( C(i-1,3) )   ( C(i,3) )

The last three rows are trivial and can be filled from the recurrence equations above.

(.   .   .   .)  ( C(i-1,0) )   ( C(i,0) )
(1   1   0   0)  ( C(i-1,1) ) = ( C(i,1) )
(0   1   1   0)  ( C(i-1,2) )   ( C(i,2) )
(0   0   1   1)  ( C(i-1,3) )   ( C(i,3) )

The first row, for C(i,0), depends on what is supposed to happen when k = 0. We know that C(i,0) = 1 for all i when k=0. So the matrix reduces to

(.   .   .   .)  ( C(i-1,0) )   ( C(i,0) )
(1   1   0   0)  ( C(i-1,1) ) = ( C(i,1) )
(0   1   1   0)  ( C(i-1,2) )   ( C(i,2) )
(0   0   1   1)  ( C(i-1,3) )   ( C(i,3) )

And this then leads to the general form:

               i
(.   .   .   .)  ( C(0,0) )   ( C(i,0) )
(1   1   0   0)  ( C(0,1) ) = ( C(i,1) )
(0   1   1   0)  ( C(0,2) )   ( C(i,2) )
(0   0   1   1)  ( C(0,3) )   ( C(i,3) )

For example if we wan’t C(4,3) we just raise the above matrix to the 4th power.

              4
(1   0   0   0)  ( 1 )   ( 1 )
(1   1   0   0)  ( 0 ) = ( 4 )
(0   1   1   0)  ( 0 )   ( 6 )
(0   0   1   1)  ( 0 )   ( 4 )

Here’s a C++ code.

#include<iostream>
using namespace std;

/*    
	C(n,r) mod m
	Using Matrix Exponentiation
	Time Complexity: O((r^3)*log(n))
	Space Complexity: O(r*r)
*/

long long MOD;

template< class T >
class Matrix
{
	public:
		int m,n;
		T *data;
		
		Matrix( int m, int n );
		Matrix( const Matrix< T > &matrix );
		
		const Matrix< T > &operator=( const Matrix< T > &A );
		const Matrix< T > operator*( const Matrix< T > &A );
		const Matrix< T > operator^( int P );
		
		~Matrix();
};

template< class T >
Matrix< T >::Matrix( int m, int n )
{
	this->m = m;
	this->n = n;
	data = new T[m*n];
}

template< class T >
Matrix< T >::Matrix( const Matrix< T > &A )
{
	this->m = A.m;
	this->n = A.n;
	data = new T[m*n];
	for( int i = 0; i < m * n; i++ )
		data[i] = A.data[i];
}

template< class T >
Matrix< T >::~Matrix()
{
	delete [] data;
}

template< class T >
const Matrix< T > &Matrix< T >::operator=( const Matrix< T > &A )
{
	if( &A != this )
	{
		delete [] data;
		m = A.m;
		n = A.n;
		data = new T[m*n];
		for( int i = 0; i < m * n; i++ )
			data[i] = A.data[i];
	}
	return *this;
}

template< class T >
const Matrix< T > Matrix< T >::operator*( const Matrix< T > &A )
{
	Matrix C( m, A.n );
	for( int i = 0; i < m; ++i )
		for( int j = 0; j < A.n; ++j )
		{
			C.data[i*C.n+j]=0;
			for( int k = 0; k < n; ++k )
				C.data[i*C.n+j] = (C.data[i*C.n+j] + (data[i*n+k]*A.data[k*A.n+j])%MOD)%MOD;		
		}
	return C;
}

template< class T >
const Matrix< T > Matrix< T >::operator^( int P )
{
	if( P == 1 ) return (*this);
	if( P & 1 ) return (*this) * ((*this) ^ (P-1));
	Matrix B = (*this) ^ (P/2);
	return B*B;
}

long long C(int n, int r)
{
	Matrix<long long> M(r+1,r+1);
	for (int i=0;i<(r+1)*(r+1);i++)
		M.data[i]=0;
	M.data[0]=1;
	for (int i=1;i<r+1;i++)
	{
		M.data[i*(r+1)+i-1]=1;
		M.data[i*(r+1)+i]=1;
	}
	return (M^n).data[r*(r+1)];
}

int main()
{
	int n,r;
	while (~scanf("%d%d%lld",&n,&r,&MOD))
	{
		printf("%lld\n",C(n, r));
	}
}

5. Using the power of prime p in n factorial
The power of prime p in n factorial is given by
εp = ⌊n/p⌋ + ⌊n/p2⌋ + ⌊n/p3⌋…
If we call the power of p in n factorial, the power of p in nCr is given by
e = countFact(n,i) – countFact(r,i) – countFact(n-r,i)
To get the result we multiply p^e for all p less than n.

#include<iostream>
using namespace std;
#include<vector>

/* This function calculates power of p in n! */
int countFact(int n, int p)
{
	int k=0;
	while (n>0)
	{
		k+=n/p;
		n/=p;
	}
	return k;
}

/* This function calculates (a^b)%MOD */
long long pow(int a, int b, int MOD)
{
	long long x=1,y=a; 
	while(b > 0)
	{
		if(b%2 == 1)
		{
			x=(x*y);
			if(x>MOD) x%=MOD;
		}
		y = (y*y);
		if(y>MOD) y%=MOD; 
		b /= 2;
	}
	return x;
}

long long C(int n, int r, int MOD)
{
	long long res = 1;
	vector<bool> isPrime(n+1,1);
	for (int i=2; i<=n; i++)
		if (isPrime[i])
		{
			for (int j=2*i; j<=n; j+=i)
				isPrime[j]=0;
			int k = countFact(n,i) - countFact(r,i) - countFact(n-r,i);  
			res = (res * pow(i, k, MOD)) % MOD;
		}
	return res;
}

int main()
{
	int n,r,m;
	while (scanf("%d%d%d",&n,&r,&m))
	{
		printf("%lld\n",C(n,r,m));
	}
}

6. Using Lucas Theorem
For non-negative integers m and n and a prime p, the following congruence relation holds:
\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,
where
m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,
and
n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0
are the base p expansions of m and n respectively.
We only need to calculate nCr only for small numbers (less than equal to p) using any of the above methods.

#include<iostream>
using namespace std;
#include<vector>

long long SmallC(int n, int r, int MOD)
{
	vector< vector<long long> > C(2,vector<long long> (r+1,0));

	for (int i=0; i<=n; i++)
	{
		for (int k=0; k<=r && k<=i; k++)
			if (k==0 || k==i)
				C[i&1][k] = 1;
			else
				C[i&1][k] = (C[(i-1)&1][k-1] + C[(i-1)&1][k])%MOD;
	}
	return C[n&1][r];
}

long long Lucas(int n, int m, int p)
{
	if (n==0 && m==0) return 1;
	int ni = n % p;
	int mi = m % p;
	if (mi>ni) return 0;
	return Lucas(n/p, m/p, p) * SmallC(ni, mi, p);
}

long long C(int n, int r, int MOD)
{
	return Lucas(n, r, MOD);
}

int main()
{
    
    int n,r,p;
	while (~scanf("%d%d%d",&n,&r,&p))
	{
          printf("%lld\n",C(n,r,p));
    }
}

7. Using special n! mod p
We will calculate n factorial mod p and similarly inverse of r! mod p and (n-r)! mod p and multiply to find the result. But while calculating factorial mod p we remove all the multiples of p and write
n!* mod p = 1 * 2 * … * (p-1) * 1 * 2 * … * (p-1) * 2 * 1 * 2 * … * n.
We took the usual factorial, but excluded all factors of p (1 instead of p, 2 instead of 2p, and so on). Lets call this strange factorial.
So strange factorial is really several blocks of construction:
1 * 2 * 3 * … * (p-1) * i
where i is a 1-indexed index of block taken again without factors p.
The last block could be not full. More precisely, there will be floor(n/p) full blocks and some tail (its result we can compute easily, in O(P)).
The result in each block is multiplication 1 * 2 * … * (p-1), which is common to all blocks, and multiplication of all strange indices i from 1 to floor(n/p).
But multiplication of all strange indices is really a strange factorial again, so we can compute it recursively. Note, that in recursive calls n reduces exponentially, so this is rather fast algorithm.
Here’s the algorithm to calculate strange factorial.

int factMOD(int n, int MOD)
{
	long long res = 1;
	while (n > 1)
	{
		long long cur = 1;
		for (int i=2; i<MOD; ++i)
			cur = (cur * i) % MOD;
		res = (res * powmod (cur, n/MOD, MOD)) % MOD;
		for (int i=2; i<=n%MOD; ++i)
			res = (res * i) % MOD;
		n /= MOD;
	}
	return int (res % MOD);
}

But we can still reduce our complexity.
By Wilson’s Theorem, we know (n-1)!\ \equiv\ -1 \pmod n for all primes n. SO our method reduces to:

long long factMOD(int n, int MOD)
{
	long long res = 1;
	while (n > 1)
	{
		res = (res * pow(MOD - 1, n/MOD, MOD)) % MOD;
		for (int i=2, j=n%MOD; i<=j; i++)
			res = (res * i) % MOD;
		n/=MOD;
	}
	return res;
}

Now in the above code we are calculating (-1)^(n/p). If (n/p) is even what we are multiplying by 1, so we can skip that. We only need to consider the case when (n/p) is odd, in which case we are multiplying result by (-1)%MOD, which ultimately is equal to MOD-res. SO our method again reduces to:

long long factMOD(int n, int MOD)
{
	long long res = 1; 
	while (n > 0)
	{
		for (int i=2, m=n%MOD; i<=m; i++)
			res = (res * i) % MOD;
		if ((n/=MOD)%2 > 0) 
			res = MOD - res;
	}
	return res;
}

Finally the complete code here:

#include<iostream>
using namespace std;
#include<vector>

/* This function calculates power of p in n! */
int countFact(int n, int p)
{
	int k=0;
	while (n>=p)
	{
		k+=n/p;
		n/=p;
	}
	return k;
}

/* This function calculates (a^b)%MOD */
long long pow(int a, int b, int MOD)
{
	long long x=1,y=a; 
	while(b > 0)
	{
		if(b%2 == 1)
		{
			x=(x*y);
			if(x>MOD) x%=MOD;
		}
		y = (y*y);
		if(y>MOD) y%=MOD; 
		b /= 2;
	}
	return x;
}

/* 	Modular Multiplicative Inverse
	Using Euler's Theorem
	a^(phi(m)) = 1 (mod m)
	a^(-1) = a^(m-2) (mod m) */
long long InverseEuler(int n, int MOD)
{
	return pow(n,MOD-2,MOD);
}

long long factMOD(int n, int MOD)
{
	long long res = 1; 
	while (n > 0)
	{
		for (int i=2, m=n%MOD; i<=m; i++)
			res = (res * i) % MOD;
		if ((n/=MOD)%2 > 0) 
			res = MOD - res;
	}
	return res;
}

long long C(int n, int r, int MOD)
{
	if (countFact(n, MOD) > countFact(r, MOD) + countFact(n-r, MOD))
		return 0;

	return (factMOD(n, MOD) *
			((InverseEuler(factMOD(r, MOD), MOD) * 
			InverseEuler(factMOD(n-r, MOD), MOD)) % MOD)) % MOD;
}

int main()
{    
	int n,r,p;
	while (~scanf("%d%d%d",&n,&r,&p))
	{
		printf("%lld\n",C(n,r,p));
	}
}

-fR0D

Written by fR0DDY

July 31, 2011 at 5:30 PM

Counting Problems

with 18 comments

Problem 1: Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to  K?

Also called the Subset Sum Problem, in this problem, the number of times we can use a particular number is limited i.e. we can use a number only once. This problem can be done in two ways
1> Binary Representation of Numbers and
2> DP

1> Using Binary Representation of Numbers
First lets discuss the common approach for iterating through all subsets of a set. Mathematics tells us that the total number of subsets of a set is 2n. THe easier way to do this is in any programmin language is to represent each element of a set by a single bit of the number. So for example, if we have 3 elements in a set then we have 8 subsets. or we can iterate from 0 to 7 to get all subsets as

Number Binary Representation
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

So if we let 1 in the binary represent that the number is selected and 0 that the number is not selected, we actually have all the subsets of the set. We can use this approach to solve the above problem by iterating through all subsets and finding whether the sum is equal to the required sum. The point to be noted is that this approach is quite slow since for a worst case scenario we iterate through all the 2n cases. Also checking each bit takes time. Here’s a simple C++ implementation of the above logic. Below is a program which takes as input N numbers and M the required subset sum and outputs Yes if the subset sum M is possible and No otherwise.

int a[21];
int main()
{
    int t,N,M,i,j,k,sum;
    bool F;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for (i=0;i<N;i++)
            scanf("%d",&a[i]); 

        F=0;
        j=1<<N;
        for (i=1;i<j && F==0;i++)
        {
            sum=0;
            for (k=0;k<N;k++)
            {
                if ((i & (1<<k)) == (1<<k))
                   sum += a[k];
            }
            if (sum == M)
            {
                F=1;
                printf("Yes\n");
            }

        }
        if (F==0)
           printf("No\n");

    }
}

The time complexity of the above code is O(2n). We also have a O(2n/2) algorithm, where we divide the input numbers into two equal subsets. Then we calculate the sum of subsets of each of the two subset. We then iterate through the sums of one subset and check whether M-sum is present in the sums of the other subset. If yes, we get our desired result. If there are no such values we print no.

#include<iostream>
using namespace std;
#include<set>

int a[21];
int main()
{
    int t,N,M,i,j,k,sum,x;
    set<int> s1,s2;
    set<int>::iterator l;
    scanf("%d",&t);
    
    while(t--)
    {
        scanf("%d%d",&N,&M);
        s1.clear();
        s2.clear();
        for (i=0;i<N;i++)
            scanf("%d",&a[i]); 

        
        j=1<<(N/2);
        for (i=0;i<j;i++)
        {
            sum=0;
            for (k=0;k<N/2;k++)
            {
                if ((i & (1<<k)) == (1<<k))
                   sum += a[k];
            }
            s1.insert(sum);
        }
        
        x=N-N/2;
        j=1<<x;
        for (i=0;i<j;i++)
        {
            sum=0;
            for (k=0;k<x;k++)
            {
                if ((i & (1<<k)) == (1<<k))
                   sum += a[k+N/2];
            }
            s2.insert(sum);
        }
        
        for (l=s1.begin();l!=s1.end();l++)
        {
            if (binary_search(s2.begin(),s2.end(),M-*l))
            {
               printf("Yes\n");
               break;
            }
        }
        if (l==s1.end())
           printf("No\n");
    }
}

2> DP Approach
This is the other approach to solving this problem. This method takes into account that the possible sum’s after including a number, are all previous possible sum’s plus the new number. So we only check whether x-ai is a possible sum, if yes x is also a possible sum. We iterate from M (maximum possible sum) to ai because we cannot include a number twice. Here’s the C++ implementation of the above program using DP approach.

int m[30000],a[21];
int main()
{
    int t,N,M,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        for (i=0;i<N;i++)
            scanf("%d",&a[i]);
        for (i=0;i<=M;i++)
            m[i]=0;
       	m[0]=1;
        for(i=0; i<N; i++)
        	for(j=M; j>=a[i]; j--)
        		m[j] |= m[j-a[i]];
  		if (m[M])
  		   printf("Yes\n");
	   else
	       printf("No\n");
    }
}

Problem 2: Given that the ai‘s are unlimited i.e you can use the numbers in the subset as many times as you want find whether a particular sum M is possible and if possible how many ways are there to do it?

Also called the Counting Change Problem, this problem is a variation of the above problem and we just need to change the direction of the second loop in the above problem. Here’s a program to find the number of ways to change a amount of Rs. 100 using the coins and notes of RS. 1,2,5,10,20,50,100.

int main()
{
    int coin[7]={1,2,5,10,20,50,100},i,j,x,c;
    x=100;
    vector<long long> ways(x+1,0);
    ways[0]=1;
    for (i=0;i<7;i++)
    {
      c=coin[i];
      for (j=c;j<=x;j++)
          ways[j]+=ways[j-c];
    }
    cout<<ways[100]<<endl;
}

More variations of the above problem can be minimizing the number of elements required to get a particular sum.

Problem 3: Find the number of ways of writing a number as the sum of positive integers?

Also called the Partition Function P of n, it is denoted by P(n). For example,

5 5
  4+1
  3+2
  3+1+1
  2+2+1
  2+1+1+1
  1+1+1+1+1

Euler invented a generating function which gives rise to a recurrence equation in P(n),
Recurrence Equation in P(n)
Below is a program to calculate P(n). It can easily modified to include large numbers.

#include<iostream>
using namespace std;
#include<map>

map <int , long long> P;
 
long long Calculate_Pn(long long n)
{
  if (n < 0) 
     return 0;
 
  long long Pn = P[n];
 
  if (Pn == 0) 
  {
     long long k; 
     for (k = 1; k <= n; k++) 
     { 
         // A little bit of recursion 
         long long n1 = n - k * (3 * k - 1) / 2; 
         long long n2 = n - k * (3 * k + 1) / 2; 
    
         long long Pn1 = Calculate_Pn(n1); 
         long long Pn2 = Calculate_Pn(n2); 
    
         // elements are alternately added 
         // and subtracted 
         if (k % 2 == 1) 
            Pn = Pn + Pn1 + Pn2; 
         else 
              Pn = Pn - Pn1 - Pn2; 
    }
       P[n]=Pn;
  } 
  return Pn;
}

int main()
{
    long long i;
    P[0]=1;
    while (scanf("%lld",&i)!=EOF)
          printf("%lld\n",Calculate_Pn(i));
}

Happy Coding!!!
-fR0D

Written by fR0DDY

July 21, 2009 at 10:05 AM

Programming Multiplicative Functions

with 9 comments

In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then f(ab) = f(a)f(b).

This type of functions can be programmed in quick time using the multiplicative formmula. Examples of multiplicative functions include Euler’s totient function, Möbius function and divisor function.

A multiplicative function is completely determined by its values at the powers of prime numbers, a consequence of the fundamental theorem of arithmetic. Thus, if n is a product of powers of distinct primes, say n = pa qb …, then f(n) = f(pa) f(qb) …

Lets take an example. If we need to calculate the divisor of 12 then div(12) = div(2231) or div(22)div(31). If we are calculating it for a range then it becomes even more easier. We only need to calculte the div(22)part because the div(31) part will already be present in the array. So lets look at an sample code for calculating the divisor of all numbers from 1 to 10000000.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int A[10000000]={0};
int main()
{ 

    int isprime[3163],d,n,e,p,k,i;

    for (n=2;n<3163;n++)
        isprime[n]=1;

    //Sieve for Eratosthenes for Prime
    //Storing the smallest prime which divides n.
    //If A[n]=0 it means it is prime number.
    for(d=2;d<3163;d++)
    {
        if(isprime[d])
        {
            for (n=d*d;n<3163;n+=d)
            {
                isprime[n]=0;
                A[n]=d;
            }
            for (;n<=10000000;n+=d)
                A[n]=d;
        }
    }

    //Applying the formula
    //Divisor(N)=Divisors(N/p^f(N,p))*(f(N,p)+1)
    A[1]=1;
    for(n=2;n<=10000000;n++)
    {
        if (A[n]==0)
           A[n]=2;
        else
        {
           p=A[n],k=n/p,e=2;
           while (k%p==0)
                 k/=p,e++;
           A[n]=A[k]*e;
        }
    }
    printf("time=%.3lf sec.\n",
    (double) (clock())/CLOCKS_PER_SEC);
    while (scanf("%d",&i),i)
    {
          printf("%d\n",A[i]);
    }
    return 0;
}

If you run the above program you will be able to see how fast have we made this program. Similar techniques can be used to calculate the divisor function or the sum of squares of divisors which is also called sigma2. The general formula for calculating sigma function is :

sigma_x

sigma_x

or sigma_x

-fR0DDY

Written by fR0DDY

April 13, 2009 at 6:31 AM

Farey Sequence/Series

with 2 comments

Farey Sequence of order N is the ascending sequnce of all reduced fractions between 0 and 1 that have denominators <=N. For example, the Farey Series of order 4 is

01, 14, 13, 12, 23, 34, 11

This series can be generated using the following recurrence relation

x0=0     y0=1
x1=1     y1=N
xk+2= floor((yk+N)/yk+1)xk+1xk
yk+2= floor((yk+N)/yk+1)yk+1yk

The C++ Implementation would look something like this :

x1=0,y1=1,x2=1,y2=N;
x=1;y=N;
printf("%.0lf/%.0lf, %.0lf/%.0lf",x1,y1,x2,y2);
while (y!=1.0)
{
    x=floor((y1+N)/(y2))*x2-x1;
    y=floor((y1+N)/(y2))*y2-y1;
    printf(", %.0lf/%.0lf",x,y);
    x1=x2,x2=x,y1=y2,y2=y;
}
printf("\n");

Note that the number of terms in the Farey Series is given by :
Length
where phi(m) is the Euler Toteint Function.


Did You Know?
77 x 999 = 777 x 99 and
112 x 112 = 12544 and its back order
211 x 211 = 44521

NJOY!!!
-fR0D

Written by fR0DDY

March 1, 2009 at 10:04 AM

Posted in Maths, Programming

Tagged with , , , , ,

%d bloggers like this: