Basic Math & Number Theory
View on GitHubBasic Math and Number Theory
Math and number theory are important components of competitive programming, as they provide an important foundation for understanding and solving programming problems. Math and number theory can be used to solve problems related to algorithms, data structures, and other areas of computer science. Math and number theory can be used to develop efficient algorithms, analyze data structures, and understand the underlying principles behind problem-solving. They are also relevant to game theory, cryptography, and other areas of computer science. Math and number theory provide the necessary skills and knowledge to solve complex problems, and are essential for success in competitive programming.
This repository includes materials for learning and understanding basic math and number theory concepts. The topics covered in this repository include, but are not limited to:
- Introduction to Number Theory
- Divisibility Rules
- Perfect Squares
- Logarithm Basics
- Binary Exponentiation
- Euclidean Algorithm to find the GCD
- Fibonacci Numbers
- Primality Tests
- Sieve of Eratosthenes
- Modular Arithmetic
- LCM
- Factorials
And we are here to learn them in practice and get benefit of using them.
Enjoy Math and Number Theory!
My Session @ ICPC SCU
Useful Materials
Reading Materials
Introduction
Primes
- Primality Test | Set 1 (GeeksforGeeks)
- Sieve of Eratosthenes (GeeksforGeeks)
- Sieve of Eratosthenes (CP-Algorithms)
Modular Arithmetic
- Modular Arithmetic (GeeksforGeeks)
- Compute an answer under modulo 1e9 + 7 (GeeksforGeeks)
- How to compute n! under modulo p efficiently (GeeksforGeeks)
- How to compute mod for a big number (GeeksforGeeks)
- How to find the value of y mod 2 raised to the power x efficiently (GeeksforGeeks)
Video Materials
Introduction
- Elementary Math (Dr.Mostafa Saad)
- Factorization (Mr.Algorithms)
- Factorization (Dr.Mostafa Saad)
- GCD (Mr.Algorithms)
- LCM (Mr.Algorithms)
- Binary Exponentiation (Errichto)
- Factorial (Dr.Mostafa Saad)
- Fibonacci, GCD, LCM, Power (Dr.Mostafa Saad)
Primes
Modular Arithmetic
- Modular Arithmetic (Mr.Algorithms)
- Modular Arithmetic (Errictho)
- Modular Arithmetic (Dr.Mostafa Saad)
Practice Problems
- The last 2 digits (CF - Assiut's sheet)
- Zara welcomes visitors (CF - Luxor's Marathon)
- Player and Time (CF - SCU's Contest)
- Player and Sum (CF - SCU's Contest)
- Modulo Sum (CF - SCU's Contest)
- Divisible (CF - Assiut's Sheet)
- GCD and LCM (CodeChef)
- Exponentiation (CSES)
- Big Mod (UVA)
- Counting Divisors (CSES)
- Prime Factorization (CF)
- Div Game (AtCoder)
- Common Divisors (CSES)
- Product 1 Modulo N (CF)
- Back to Intermediate (UVA)
- The 3n + 1 problem
- One Prime (CF - Assiut's Sheet)
- Primes from 1 to n (CF - Assiut's Sheet)
- Finding the Kth Prime (SPOJ)
- Integer Factorization (SPOJ)
- Bubble Sort (UVA)
- Very Big Perfect Squares (UVA)
- Numbering Roads (UVA)
- Brick Game (UVA)
- Perfection (UVA)
- Digit Counting (UVA)