Number Theory Utilities

Greatest Common Divisor

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Least Common Multiple

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

Fast Exponentiation

long long power(long long base, long long exp) {
    long long result = 1;
    while (exp) {
        if (exp & 1) result *= base;
        base *= base;
        exp >>= 1;
    }
    return result;
}

Prime Sieve (Euler's Sieve)

const int N = 1000009;
vector<int> primes;
bool composite[N];

void generatePrimes(int limit) {
    for (int i = 2; i <= limit; ++i) {
        if (!composite[i]) primes.push_back(i);
        for (int j = 0; j < primes.size() && primes[j] * i <= limit; ++j) {
            composite[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

Modular Combination (using Modular Inverse)

const int MOD = 1e9 + 7;
vector<long long> factorial;

long long modPow(long long x, long long p) {
    long long res = 1;
    while (p) {
        if (p & 1) res = res * x % MOD;
        x = x * x % MOD;
        p >>= 1;
    }
    return res;
}

long long modInv(long long x) {
    return modPow(x, MOD - 2);
}

void precompute(int n) {
    factorial.assign(n + 1, 1);
    for (int i = 1; i <= n; ++i)
        factorial[i] = factorial[i - 1] * i % MOD;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return factorial[n] * modInv(factorial[r]) % MOD * modInv(factorial[n - r]) % MOD;
}

Base Conversion (2–36)

Decimal to base:

string toBase(int num, int base) {
    static const char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string res;
    do {
        res = digits[num % base] + res;
        num /= base;
    } while (num);
    return res;
}

String to decimal:

int fromBase(const string& s, int base) {
    int res = 0;
    for (char c : s) {
        int digit = isdigit(c) ? c - '0' : toupper(c) - 'A' + 10;
        res = res * base + digit;
    }
    return res;
}

Union-Find Structure

Basic Disjoint Set (path compression)

vector<int> parent;

void init(int n) {
    parent.resize(n + 1);
    for (int i = 1; i <= n; ++i) parent[i] = i;
}

int findSet(int x) {
    return parent[x] == x ? x : parent[x] = findSet(parent[x]);
}

void unionSets(int a, int b) {
    parent[findSet(a)] = findSet(b);
}

Union by Size

vector<int> parent, sz;

void init(int n) {
    parent.resize(n + 1);
    sz.assign(n + 1, 1);
    for (int i = 1; i <= n; ++i) parent[i] = i;
}

int findSet(int x) {
    return parent[x] == x ? x : parent[x] = findSet(parent[x]);
}

void unionSets(int a, int b) {
    a = findSet(a);
    b = findSet(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
}

With Distance to Root

vector<int> parent, dist;

void init(int n) {
    parent.resize(n + 1);
    dist.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i) parent[i] = i;
}

int findSet(int x) {
    if (parent[x] != x) {
        int root = findSet(parent[x]);
        dist[x] += dist[parent[x]];
        parent[x] = root;
    }
    return parent[x];
}

void unionSets(int a, int b, int weight) {
    int ra = findSet(a), rb = findSet(b);
    if (ra != rb) {
        parent[ra] = rb;
        dist[ra] = dist[b] + weight - dist[a];
    }
}

Dynamic Programming

0/1 Knapsack (2D)

int capacity, n;
cin >> capacity >> n;
vector<int> wt(n), val(n);
for (int i = 0; i < n; ++i) cin >> wt[i] >> val[i];

vector<vector<int>> dp(n, vector<int>(capacity + 1, 0));
for (int j = wt[0]; j <= capacity; ++j)
    dp[0][j] = val[0];

for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= capacity; ++j) {
        if (j < wt[i])
            dp[i][j] = dp[i - 1][j];
        else
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt[i]] + val[i]);
    }
}
cout << dp[n - 1][capacity] << endl;

0/1 Knapsack (1D optimization)

int capacity, n;
cin >> capacity >> n;
vector<int> wt(n), val(n);
for (int i = 0; i < n; ++i) cin >> wt[i] >> val[i];

vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; ++i)
    for (int j = capacity; j >= wt[i]; --j)
        dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
cout << dp[capacity] << endl;

Unbounded Knapsack

int capacity, n;
cin >> capacity >> n;
vector<int> wt(n), val(n);
for (int i = 0; i < n; ++i) cin >> wt[i] >> val[i];

vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; ++i)
    for (int j = wt[i]; j <= capacity; ++j)
        dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
cout << dp[capacity] << endl;