## DEV Community

Mahesh Sv

Posted on • Updated on

# Math101 for Competitive Programming

In this Article we will discuss the essential needs of Math Knowledge for Starting Competitive Programming.

Table of Content:

2. Modular Arithmetic Properties
3. Inclusion Exclusion principle and programming applications

Birthday Paradox actually states. How many people must be there in a room to make the probability p% that at-least two people in the room have same birthday?. Naive solution is the by finding p(different) and subtracting from 1 equaling it to p(same). After solving you will get the N. Instead of that you can simply use the formula which is actually derived from the above equation is

``````sqrt(2*365*log(1/(1-p)))
``````

## 2. Modular Arithmetic Properties:

In competitive programming, Modular Arithmetic Properties are essential tools in solving big number problems. In the Problem statement when they ask to print solution in mod(107+9). It not as sample as it seems. You might get large number before applying mod to it. To simplify, You need have idea on Modular Arithmetic Properties

``````( a + b ) mod p
``````

Use this Formula

`(a+b) mod p = ((a mod p) + (b mod p))mod p`

`(a*b) mod p`

Same case here but when they said to multiply and which result might end up overflow. Use this Formula

`(a*b) mod p = ((a mod p)*(b mod p))mod p`

## 3. Inclusion Exclusion principle and programming applications:

The principle of inclusion-exclusion says that in order to count only unique ways of doing a task, we must add the number of ways to do it in one way and the number of ways to do it in another and then subtract the number of ways to do the task that are common to both sets of ways.

And Also Worth Mentioning
L.C.M and G.C.D code
You can see all the code here in