COMPLETE STEP BY STEP MATHEMATICS FOR COMPETITIVE PROGRAMMING

April 25, 2022

COMPLETE STEP BY STEP MATHEMATICS FOR COMPETITIVE PROGRAMMING

Mathematics required for Competitive Programming...

Competitive Programming (CP) requires a lot of mathematics. Generally , these maths concept come in the picture of different types of problems .Directly or indirectly these maths concept makes solution to solvable in given Time and Space constraints.

Here the complete list of mathematics is given which are must be familiar to any Competitive Programmer.

1. Adhoc/Brute force approach problems...

This section contains those concepts which are generally either Formula based or follow straight forward approach to solve the Problems. For example , Problem to find compound interest over a given period of time , area of different 2D and 3D Geometrical figures etc.

2. Big Integer based problems...

During the contest most of the time, size of the data becomes larger than the capacity of Variable. In these situation, We need to handle Big data(generally integer) efficiently to avoid the data loss. In such situation, Concept to handling Big integer plays an important role . Given link will give you idead to handle Big Integer.

Big Integer handling in JAVA

Handling Big Integer in C++

3. Series based problems....

Some specific set of problems that demands the concept of sequences and series which are generally studied in High schools..

Here the gives a set of problems based on Sequences and Series...

Problem based on Sequences and Series

Concepts of Number theory..

4.Modular arithematic Problems...

Modular arithmetic plays a very important role in CP. Most of the time , It requires to output of the result in the form of answer mod (1e9 +7) . There are also many situation like Clock problem or other problems having periodic properties need Modular arithmetic concepts. Here the few links to Understand the basics of modular arithmetic..

Basic Modular arithmetic

Basic Modular arithmetic 2

5. Exponentiation based problems...

What happens If someone asks you to find the value of 35 raise to 7 !!! Generally It's tedious to find such a large value and we do favour of use calculators. But what happened if this calculation is also tedious for your smart calculator !!!

Similar situation occurs during the solving the CP problems. Generally Our answer of exponentiation cross the Time and Space limits. In those situation , We need to handle the operations more smartly. Here links are given that clarify the process to handle Big Exponentiation.

C++ code to handle Big exponentiation

Concept behind the Exponentiation

6.Modular multiplicative Inverse...

Concept of Modular multiplicative inverse plays a very important role in the number theory. Lots of Theories , Algorithms uses the concept of Modular Multiplicative Inverse.

Here the given link provides you the clear Idea about Modular Multiplicative Inverse....

Concept of Modular Multiplicative Inverse

7.Euclid's algorithm...

Euclid's algorithm is used to find the GCD of two or more numbers. But finding the GCD of numbers is not the sole application of Euclid's algorithm , there are lots of section Number theory which uses the Euclid's Theorem as a tool to solve different type of problems.

Here the given link gives the Idea of Euclid's Algorithm..

Concept and code of Euclid's algorithm

8.Extended Euclid's algorithm...

Problems that involve finding the value of variables which are related to each other by a specific linear equation uses the concept of Extended Euclid's Algorithm.

Here the link given clarify the concept behind the Extended Euclid's Algorithm..

Concept of Extended Euclid's Algorithm.

9. Application of Extended Euclid's algorithms....

Here the given link provides the different application of Extended Euclid's Algorithm..

Euclid Problem

10.Linear Diophantine Equation..

A set of problems based on linear equation frequently asked in CP contest. the knowledge Linear Diophantine Equation is necessary to solve these types of problems .

Here the given link provides the complete idea behind this type of equation.

Linear Diophantine Equation

11.Chinese Remainder Theorem..

Concepts and theorem applied on prime numbers....

12. Sieve of Eratosthenes...

Finding a prime number in a given interval is very important in many of the problems of CP and also a very important concept in the Number theory. Sieve of Eratosthenes is the efficient method to find the Prime numbers in a given interval.

Here the given link give the Clear cut Idea of sieve Of Eratosthenes ...

Sieve of Eratosthenes

13.Euler's Totient function...

Totient function (denoted by