Number Theory and Algebra for Competitive Programming

Topics

• Modular Arithmetic Basics [1st meet]

  Modular Arithmetic for Beginners - Codeforces

  If you're new to the world of competitive programming, you may have noticed that some tasks, typically combinatorial and probability tasks, have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo $$$10^9 + 7$$$".

  https://codeforces.com/blog/entry/72527?fbclid=IwAR1Eb8t0ZeECfy9GeaOewFCwobop1x8jUKNeS6Ax6S5J1HcU1U3sguMlJVU

  

  1. Addition
  2. Subtraction
  3. Multiplication
  4. Division
     • Explain what does modular inverse mean?
     • Fermat's little theorem
     • Euler's generalization of Fermat's little theorem [this includes the knowledge of phi function, so should be covered later]
  5. Euclidean Algorithm and its extension: GCD and LCM
  6. Binary Exponentiation

     Matrix Exponentiation tutorial + training contest - Codeforces

     tl;dr - video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.com/gym/102644 (register by finding this contest in GYM instead of using the link directly)video editorial: part 1 (ABCDEF) and part 2 (GHI) codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices) The youtube tutorial ( link) focuses on intuition and graph-like visualization .

     https://codeforces.com/blog/entry/80195

     

     [Tutorial]A Complete Guide on Matrix Exponentiation - Codeforces

     The concept of matrix exponentiation in its most general form is very useful in solving questions that involve calculating the $$$n^{th}$$$ term of a linear recurrence relation in time of the order of log(n).

     https://codeforces.com/blog/entry/67776

     

     • Fibonacci
  7. Linear Diophantine Equations

• Prime Numbers
  1. Sieve of Eratosthenes
  2. Primality Tests
  3. Integer Factorization [this includes divisors]

• Number Theoretic Functions
  1. Totient Function and Euler's Generalization
  2. Number of divisors [lite this is basic maths]
  3. Sum of divisors [this also, can go over this quickly though]

Problems

• ASC 5 Problem A (Hard)

Number theory practice problems. - Codeforces

Nothing is well understood unless we can apply it to solve some problems. Currently, I am learning number theory and there is no good classified list of problems for number theory. So, It is difficult to find some problem based on a specific topic.

https://codeforces.com/blog/entry/49494