Competitive Programming and Problem Solving 101

Number Theory

1. Euclidean Algorithm – Greatest Common Divisor
2. Lowest Common Multiple of Two Number
   1. UVa 11388 – GCD LCM
3. Primality Test – Naive Methods
4. Sieve of Eratosthenes – Generating Primes
   1. Segmented Sieve of Eratosthenes
5. Prime Number Theorem
6. Prime Factorization of an Integer
   1. Number of Divisors of an Integer
      1. Highly Composite Numbers
      2. Upper Bound for Number Of Divisors
      3. Divisor Summatory Function
   2. Sum of Divisors of an Integer
7. Introduction to Modular Arithmetic
   1. UVa 10407 – Simple division
8. Extended Euclidean Algorithm
   1. Linear Diophantine Equation
9. Simple Hyperbolic Diophantine Equation
10. Introduction to Number Systems
    1. Bitwise Operators
    2. Bit Manipulation
11. Factorial
    1. Number of Digits of Factorial
    2. Prime Factorization of Factorial
    3. Number of Trailing Zeroes of Factorial
    4. Leading Digits of Factorial
12. Modular Exponentiation
    1. Repeated Squaring Method for Modular Exponentiation
13. Euler Totient or Phi Function
    1. Euler Phi Extension and Divisor Sum Theorem
       1. SPOJ LCMSUM – LCM Sum
    2. Euler’s Theorem and Fermat’s Little Theorem
    3. Sum of Co-prime Numbers of an Integer New!!
14. Modular Multiplicative Inverse
    1. Modular Inverse from 1 to N
15. Chinese Remainder Theorem
    1. Chinese Remainder Theorem Part 1 – Coprime Moduli
    2. Chinese Remainder Theorem Part 2 – Non Coprime Moduli
16. Multiplicative Function New!!
    1. GCD Sum Function New!!

Combinatorics

1. Stars and Bars Theorem
2. Prufer Code
   1. Prufer Code: Linear Representation of a Labeled Tree
   2. Application of Prufer Code: Random Tree Generation, Cayley’s Formula and Building Tree from Degree Count
3. Lucas Theorem – Proof and Applications New!!

Contest Analysis

1. Contest Analysis: IUT 6th National ICT Fest 2014, UVa 12830 – 12839
2. Contest Analysis: BUET Inter-University Programming Contest – 2011, UVa 12424 – 12432