Linear Sieve for Prime Numbers (O(2N))

bool composite[N];
int primes[N], prime_count;

void build_sieve(int limit) {
    for (int num = 2; num <= limit; num++) {
        if (!composite[num]) {
            primes[prime_count++] = num;
        }
        for (int j = 0; j < prime_count && num * primes[j] <= limit; j++) {
            composite[num * primes[j]] = true;
            if (num % primes[j] == 0) break;
        }
    }
}

Extended Euclidean Algorithm

int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int gcd = extended_gcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

Additional Number Theory Concepts

• Solving Multiple Congruence Equations: For equations x ≡ d₁ mod m₁ and x ≡ d₂ mod m₂, the solution is x ≡ dx mod mx, where mx = lcm(m₁, m₂).

• Modular Inverse: For ax ≡ 1 mod p, the enverse of a modulo p (when p is prime) is a^(p-2). Can be computed via recurrence: inv[i] = (p - p/i) * inv[p % i] % p.

• Fermat's Little Theorem: (a^b) % p = a^(b % (p-1)) when p is prime.

Binary Indexed Tree (Fenwick Tree)

int query(int index) {
    int total = 0;
    while (index > 0) {
        total += tree[index];
        index -= index & -index;
    }
    return total;
}

void update(int index, int value) {
    while (index <= n) {
        tree[index] += value;
        index += index & -index;
    }
}

STL Heap Operaitons

#include <algorithm>

int main() {
    std::make_heap(heap, heap + size);
    std::push_heap(heap, heap + (++size));
    std::pop_heap(heap, heap + (size--));
    // Use greater<int>() or custom comparator for min-heap
}

Fast Exponentiation and Multiplication

int fast_pow(int base, int exponent) {
    int result = 1;
    while (exponent > 0) {
        if (exponent & 1) result *= base;
        base *= base;
        exponent >>= 1;
    }
    return result;
}

int fast_multiply(int a, int b) {
    int product = 0;
    while (b > 0) {
        if (b & 1) product += a;
        a += a;
        b >>= 1;
    }
    return product;
}

Convex Hull (Graham Scan)

#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

struct Point { int x, y; };

int cross_product(Point a, Point b, Point c) {
    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
}

double distance(Point a, Point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

vector<Point> convex_hull(vector<Point>& points) {
    int n = points.size();
    if (n <= 3) return points;
    
    // Find lowest point
    int min_index = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[min_index].y || 
           (points[i].y == points[min_index].y && points[i].x < points[min_index].x)) {
            min_index = i;
        }
    }
    swap(points[0], points[min_index]);
    
    // Sort by polar angle
    sort(points.begin() + 1, points.end(), [&](Point a, Point b) {
        int cp = cross_product(a, b, points[0]);
        return cp > 0 || (cp == 0 && distance(a, points[0]) < distance(b, points[0]));
    });
    
    vector<Point> hull;
    hull.push_back(points[0]);
    hull.push_back(points[1]);
    hull.push_back(points[2]);
    
    for (int i = 3; i < n; i++) {
        while (hull.size() >= 2 && 
               cross_product(points[i], hull.back(), hull[hull.size()-2]) >= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    return hull;
}

KMP String Matching

void compute_lps(string pattern, vector<int>& lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < pattern.length()) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int kmp_search(string text, string pattern) {
    vector<int> lps(pattern.length());
    compute_lps(pattern, lps);
    
    int count = 0;
    int i = 0, j = 0;
    while (i < text.length()) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == pattern.length()) {
            count++;
            j = lps[j - 1];
        } else if (i < text.length() && pattern[j] != text[i]) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
    return count;
}

Binary Lifting for LCA

const int LOG = 17;
int depth[N], parent[N][LOG], max_edge[N][LOG];
vector<pair<int, int>> graph[N];

void dfs(int node, int par, int weight) {
    parent[node][0] = par;
    max_edge[node][0] = weight;
    depth[node] = depth[par] + 1;
    
    for (int i = 1; i < LOG; i++) {
        if (depth[node] < (1 << i)) break;
        parent[node][i] = parent[parent[node][i-1]][i-1];
        max_edge[node][i] = max(max_edge[node][i-1], 
                               max_edge[parent[node][i-1]][i-1]);
    }
    
    for (auto [neighbor, w] : graph[node]) {
        if (neighbor != par) {
            dfs(neighbor, node, w);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    
    int max_weight = -1e9;
    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG; i++) {
        if (diff & (1 << i)) {
            max_weight = max(max_weight, max_edge[u][i]);
            u = parent[u][i];
        }
    }
    
    if (u == v) return max_weight;
    
    for (int i = LOG-1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            max_weight = max(max_weight, max(max_edge[u][i], max_edge[v][i]));
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return max(max_weight, max(max_edge[u][0], max_edge[v][0]));
}