Basic Maths For CP

GCD and LCM

The GCD (Greatest Common Divisor) of two numbers is defined as the largest integer that divides both the numbers. For example, 2 is the GCD of 4 and 6. From this concept, follows something called co-primes. Two numbers are said to be co-prime if their GCD is 1. For example, 9 and 8 are co-primes because their GCD is 1.

LCM (Least Common Multiple) is defined as the smallest integer that is divisible by both the numbers. For example, 10 is the LCM of 2 and 5.

Euclid's Algorithm

Consider two numbers a and b. The procedure of Euclid's algorithm can be broken down into a sequence of equations,

a = q₀b + r₀
b = q₁r₀ + r₁
r₀ = q₂r₁ + r₂
r₁ = q₃r₂ + r₃
...

If a is smaller than b, the first step of the algorithm swaps the numbers. For example, if a < b, the initial quotient is zero and the remainder is a. Thus, r_k is smaller than it's predecessor r_k-1.

Since the remainders decrease with every iteration, a remainder r_N must eventually equal 0, at which point this algorithm stops. The final non-zero remainder r_N-1 is the greatest common divisor for a and b.

g = gcd(a, b) = gcd(b, r₀) = gcd(r₀, r₁) = … = gcd(r_N-2, r_N-1) = r_N-1.

For proof of the algorithm, visit here.

A simple implementation of Euclid's GCD algorithm in C++ would be,

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

Once we calculate the GCD of two numbers, we can calculate the LCM very easily.

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

Combinatronics

Combinatorics is the branch of mathematics that deals with combinations of elements belonging to a finite set in accordance with some constraints.

Principle of Addition
The principle of addition states if a one task can be one done in m ways and another task which is mutually exclusive of the first task can be done in n ways, then the the number of possible ways in which either can be done is m+n.

Principle of Multiplication
The principle of multiplication states that if one task can be done in m ways and another task which is independent of the first task can be done in n ways, after the first task has been performed, then the number of possible ways in which both the tasks can be done is m×n.

Combinations of Objects
Number of ways in which you can select n objects taken r at a time. (Order does not matter.)

ⁿC_r = n! / ( r! (n - r)! )

Permutations of Objects
Number of ways you can order n objects taken r at a time. (Order matters.)

ⁿP_r = n! / (n - r)!

Stars and Bars

Theorem one

For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements.

Let us say that we need to distribute 7 cookies to 4 kids such that they all have at least 1. We can represent it as stars and bars.

                            			* * * | * | * | * *

Here the 4 kids get 3, 1, 1 and 2 cookies respectively. we can say that we can place (k-1) bars between (n-1) spaces between the stars. Thus, the answer is ⁶C^3.

This can be generalized as ^(n-1)C_(k-1).

Theorem two

For any pair of positive integers n and k, the number of k-tuples of non-negative integers whose sum is n is equal to the number of multisets of cardinality k − 1 taken from a set of size n + 1.

Let us say that we need to distribute 7 cookies among 4 kids where each kid may get none or more cookies. We can represent this situation using stars and bars as well.

		                         	* * * | | * * | * *

Here the 4 kids get 3, 0, 2 and 2 cookies respectively. So there are 10 symbols out of which 3 have to be bars. Thus, the answer is ¹⁰C₃.

This can be generalized as ^(n+k-1)C_(k-1).

Properties of Combinations

Primality

This is one of the most important concepts that you'll encounter in the world of competitive programming.

A number is said to be prime if it's divisible only by 1 and itself.

For example, 2,3 and 5 are some prime numbers. We'll now look into ways to determine whether a number is prime or not.

One of the most naive algorithms to find out if a number n is prime of not would be to run a loop from 2 to n-1, checking if any number divides the number. If any number does divide n, it's a composite number. Else it's a prime. A simple implementation in C++ would be,

bool isPrime(int x)
{
    for(int i=2;i<x;i++)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}

But there are ways to make this faster. This loop doesn't need to run until n-1. We can derive that there will be no factor greater than n/2(excluding itself). Hence the loop can run until n/2 and still give us the right answer.

For example, the factors of 10 are, 1 2 3 5 10

We can see that the largest factor excluding 10 is 5. The implementation in C++ would look something like,

bool isPrime(int x)
{
    for(int i=2;i<x/2;i++)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}

We can still make this faster. Notice that both the above implementations still visit all the possible proper factors. But to test whether a number's primality, we don't need to check for all possible factors. Consider two proper factors a and b of a number n, such that,

a*b = n

We can prove by contradiction that one of them will be lesser than or equal to sqrt(n).
Using this theorem, we can reduce the loop even further to check until sqrt(n) for any possible divisors. The implementation would be,

bool isPrime(int x)
{
    for(int i=0;i*i<=x;i++)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}

Notice that in this implementation, we hit only half the number of proper divisors.
There are many more algorithms for primality test like Fermat's little theorem, Miller-Rabin test, Solovay-Strassen. But we will not look into these just yet.