Concepts52

Category

🔷All∑Math⚙️Algo🗂️DS📚Theory

Level

AllBeginnerIntermediateAdvanced
∑MathIntermediate

Fast Exponentiation

Fast exponentiation (binary exponentiation) computes a^n using repeated squaring in O(log n) multiplications.

#binary exponentiation#fast power#modular exponentiation+11
∑MathIntermediate

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) reconstructs an integer from its remainders modulo pairwise coprime moduli and guarantees a unique answer modulo the product.

#chinese remainder theorem#crt#modular arithmetic+12
∑MathIntermediate

Linear Sieve

The linear sieve builds all primes up to n in O(n) time by ensuring each composite is marked exactly once by its smallest prime factor (SPF).

#linear sieve#smallest prime factor#spf+12
∑MathIntermediate

Prime Factorization

Prime factorization expresses any integer greater than 1 as a product of primes raised to powers, uniquely up to ordering.

#prime factorization#trial division#spf sieve+12
∑MathIntermediate

Extended Euclidean Algorithm

The Extended Euclidean Algorithm finds integers x and y such that ax + by = gcd(a, b) while also computing gcd(a, b).

#extended euclidean algorithm#bezout coefficients#gcd+12
∑MathIntermediate

Sieve of Eratosthenes

The Sieve of Eratosthenes marks multiples of each prime to find all primes up to n in O(n log log n) time.

#sieve of eratosthenes#segmented sieve#linear sieve+11
∑MathIntermediate

GCD and Euclidean Algorithm

The greatest common divisor (gcd) of two integers is the largest integer that divides both without a remainder.

#gcd#euclidean algorithm#extended euclidean+12
∑MathIntermediate

Linear Basis for XOR

A linear basis for XOR is a compact set of at most W numbers (W = number of bits) that can generate every XOR value obtainable from a multiset of numbers.

#xor basis#linear basis#gaussian elimination f2+12
∑MathAdvanced

Game Theory - Advanced Games

Sprague–Grundy (SG) theory solves impartial, normal-play, terminating games by assigning each position a nonnegative integer called its Grundy value.

#sprague-grundy#grundy number#nim-sum+12
∑MathIntermediate

Matrix Rank and Linear Independence

Matrix rank is the number of pivots after Gaussian elimination and equals the dimension of both the column space and the row space.

#matrix rank#linear independence#gaussian elimination+12
∑MathAdvanced

Berlekamp-Massey Algorithm

Berlekamp–Massey (BM) finds the shortest linear recurrence that exactly fits a given sequence over a field (e.g., modulo a prime).

#berlekamp-massey#linear recurrence#minimal polynomial+11
∑MathAdvanced

Gaussian Elimination over GF(2)

Gaussian elimination over GF(2) is ordinary Gaussian elimination where addition and subtraction are XOR and multiplication is AND.

#gaussian elimination#gf(2)#xor basis+12
12345