/CP-Workshop

CP-WORKSHOP

BASICS

Binary Exponentiation

Greatest Common Divisor

Nth Fibonacci Number

Sieve of Eratosthenes

Integer Factorization

Primality tests

Modular Arithmetic

// Addition
(a + b) % m = ((a % m) + (b % m)) % m

// Subraction
(a - b) % m = ((a % m) - (b % m)) % m

// Multiplication
(a * b) % m = ((a % m) * (b % m)) % m

// Division (We need to use Mod Inverse)
(a / b) % m != ((a % m) / (b % m)) % m

Modular Inverse

// Using Fermat's Little  theorem
// If m is prime
modInv(a, m) {
    return fastpow(a, m - 2, m);
    // pow(a, m - 2) % m
}
(a / b) % m = ((a % m) * modInv(b, m)) % m

TOPICS

Binary Search

Divide and Conquer

Disjoint Set Union (DSU)

Tries

Graphs

String Hashing (Rolling Hashing)

ADVANCED TOPICS

Dynammic Programming

Segment Tree

Tree DP

Polynomial Multiplication (FFT)

LCA (Binary Lifting)

RESOURCES

Youtube

Contests and Practice

Reading