Sorting Algorithms

Quick Sort (Manual Implementation)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100010;
ll arr[MAXN];
int n;

void quickPartition(int left, int right) {
    if (left >= right) return;
    
    int pivotIdx = (left + right) / 2;
    ll pivotVal = arr[pivotIdx];
    int i = left, j = right;
    
    while (i <= j) {
        while (arr[i] < pivotVal) i++;
        while (arr[j] > pivotVal) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++; j--;
        }
    }
    
    quickPartition(left, j);
    quickPartition(i, right);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
        
    quickPartition(0, n - 1);
    
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Merge Sort with Inversion Count

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 500010;
ll original[MAXN], temp[MAXN];
ll inversionCount = 0;
int size;

void mergeSegments(int start, int end) {
    if (start >= end) return;
    
    int mid = (start + end) / 2;
    mergeSegments(start, mid);
    mergeSegments(mid + 1, end);
    
    int leftPtr = start, rightPtr = mid + 1, writePos = start - 1;
    
    while (leftPtr <= mid && rightPtr <= end) {
        if (original[leftPtr] <= original[rightPtr]) {
            temp[++writePos] = original[leftPtr++];
        } else {
            temp[++writePos] = original[rightPtr++];
            inversionCount += mid - leftPtr + 1;
        }
    }
    
    while (leftPtr <= mid)
        temp[++writePos] = original[leftPtr++];
    while (rightPtr <= end)
        temp[++writePos] = original[rightPtr++];
        
    for (int i = start; i <= end; ++i)
        original[i] = temp[i];
}

int main() {
    cin >> size;
    for (int i = 0; i < size; ++i)
        cin >> original[i];
        
    mergeSegments(0, size - 1);
    // Output or use inversionCount as needed
    return 0;
}

Binary and Ternary Search

Integer Ternary Search

ll leftBound = ..., rightBound = ..., bestCandidate = ...;
while (rightBound - leftBound >= 3) {
    ll firstThird = leftBound + (rightBound - leftBound) / 3;
    ll secondThird = rightBound - (rightBound - leftBound) / 3;
    
    if (evaluate(firstThird) > evaluate(secondThird)) {
        bestCandidate = leftBound;
        leftBound = firstThird + 1;
    } else {
        rightBound = secondThird - 1;
    }
}

for (ll candidate = leftBound; candidate <= rightBound; ++candidate) {
    if (evaluate(candidate) < evaluate(bestCandidate))
        bestCandidate = candidate;
}

Floating Point Ternary Search

double low = ..., high = ...;
const double EPSILON = 1e-9; // Adjust based on required precision

while (low + EPSILON < high) {
    double leftMid = (2 * low + high) / 3.0;
    double rightMid = (low + 2 * high) / 3.0;
    
    if (objective(leftMid) < objective(rightMid))
        high = rightMid;
    else
        low = leftMid;
}
// Result is either low or objective(low)

Standard Binary Search

ll left = ..., right = ..., result = 0;
while (left <= right) {
    ll mid = (left + right) / 2;
    if (isValid(mid)) {
        result = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

Expression Evaluation

Infix to Postfix Conversion and Evaluation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string expr;
vector<char> ops;
vector<ll> values;
vector<int> leftChild, rightChild, nodeValue, postfixOrder;
vector<bool> isOperator;
int nodeCount = 0, stackTop = 0, totalNodes = 0;
map<char, int> bracketMatch;

void buildTree(int nodeId, int start, int end) {
    if (start == end) {
        nodeValue[nodeId] = expr[start] - '0';
        return;
    }
    
    int plusMinus = -1, multDiv = -1, expFirst = -1;
    for (int i = start; i <= end; ++i) {
        if (expr[i] == '(') {
            i = bracketMatch[i];
        } else if (expr[i] == '+' || expr[i] == '-') {
            plusMinus = i;
        } else if (expr[i] == '*' || expr[i] == '/') {
            multDiv = i;
        } else if (expr[i] == '^' && expFirst == -1) {
            expFirst = i;
        }
    }
    
    int splitPoint = (plusMinus != -1) ? plusMinus : ((multDiv != -1) ? multDiv : expFirst);
    if (splitPoint == -1) {
        buildTree(nodeId, start + 1, end - 1);
    } else {
        ops[nodeId] = expr[splitPoint];
        leftChild[nodeId] = ++nodeCount;
        buildTree(leftChild[nodeId], start, splitPoint - 1);
        rightChild[nodeId] = ++nodeCount;
        buildTree(rightChild[nodeId], splitPoint + 1, end);
    }
}

void traversePostorder(int node) {
    if (leftChild[node]) traversePostorder(leftChild[node]);
    if (rightChild[node]) traversePostorder(rightChild[node]);
    postfixOrder.push_back(node);
}

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

int main() {
    cin >> expr;
    ops.resize(expr.size() + 10);
    leftChild.resize(expr.size() + 10);
    rightChild.resize(expr.size() + 10);
    nodeValue.resize(expr.size() + 10);
    isOperator.resize(expr.size() + 10);
    
    for (int i = 0; i < expr.length(); ++i) {
        if (expr[i] == '(') {
            values.push_back(i);
        } else if (expr[i] == ')') {
            bracketMatch[values.back()] = i;
            values.pop_back();
        }
    }
    
    buildTree(1, 0, expr.length() - 1);
    traversePostorder(1);
    
    vector<ll> evalStack;
    for (int idx : postfixOrder) {
        if (!leftChild[idx]) {
            evalStack.push_back(nodeValue[idx]);
        } else {
            ll rightVal = evalStack.back(); evalStack.pop_back();
            ll leftVal = evalStack.back(); evalStack.pop_back();
            ll computed;
            
            switch (ops[idx]) {
                case '+': computed = leftVal + rightVal; break;
                case '-': computed = leftVal - rightVal; break;
                case '*': computed = leftVal * rightVal; break;
                case '/': computed = leftVal / rightVal; break;
                case '^': computed = power(leftVal, rightVal); break;
            }
            evalStack.push_back(computed);
        }
    }
    
    cout << evalStack.back() << endl;
    return 0;
}

Sparse Table for Range Queries

Basic RMQ Template

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100010;
ll sparseTable[MAXN][20];
int elementCount, queryCount;

inline ll fastInput() {
    ll val = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        val = val * 10 + (ch - '0');
        ch = getchar();
    }
    return val * sign;
}

int main() {
    elementCount = fastInput();
    queryCount = fastInput();
    
    for (int i = 1; i <= elementCount; ++i)
        sparseTable[i][0] = fastInput();
        
    for (int j = 1; (1 << j) <= elementCount; ++j) {
        for (int i = 1; i + (1 << (j-1)) <= elementCount; ++i) {
            sparseTable[i][j] = max(sparseTable[i][j-1], 
                                   sparseTable[i + (1 << (j-1))][j-1]);
        }
    }
    
    while (queryCount--) {
        int left = fastInput(), right = fastInput();
        int logLen = log2(right - left + 1);
        cout << max(sparseTable[left][logLen],
                   sparseTable[right - (1 << logLen) + 1][logLen]) << endl;
    }
    return 0;
}

Logarithm Precomputation

vector<int> logCache(maxSize + 1);
for (int i = 2; i <= maxSize; ++i)
    logCache[i] = logCache[i >> 1] + 1;

// Usage: logCache[value]

Union-Find Data Structure

Basic Disjoint Set Union

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10010;
int parent[MAXN];

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

void unite(int x, int y) {
    int rootX = findRoot(x), rootY = findRoot(y);
    parent[rootX] = rootY;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    iota(parent + 1, parent + n + 1, 1);
    
    for (int i = 0; i < m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            unite(x, y);
        } else {
            cout << (findRoot(x) == findRoot(y) ? "Y" : "N") << endl;
        }
    }
    return 0;
}

Shortest Path Algorithms

Floyd-Warshall Algoritmh

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 210;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dist[MAXN][MAXN];
int nodeCount, edgeCount;

int main() {
    cin >> nodeCount >> edgeCount;
    memset(dist, 0x3f, sizeof(dist));
    
    for (int i = 0; i < edgeCount; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], (ll)w);
    }
    
    for (int i = 1; i <= nodeCount; ++i)
        dist[i][i] = 0;
        
    for (int k = 1; k <= nodeCount; ++k)
        for (int i = 1; i <= nodeCount; ++i)
            for (int j = 1; j <= nodeCount; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                
    for (int i = 1; i <= nodeCount; ++i) {
        for (int j = 1; j <= nodeCount; ++j) {
            if (dist[i][j] < INF)
                cout << dist[i][j] << " ";
            else
                cout << -1 << " ";
        }
        cout << endl;
    }
    return 0;
}

Dijkstra's Algorithm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

const int MAXN = 100010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<int> adj[MAXN], weights[MAXN];
ll distanceTo[MAXN];
bool visited[MAXN];
int startNode, nodeCount, edgeCount;

void dijkstra() {
    fill(distanceTo, distanceTo + nodeCount + 1, INF);
    priority_queue<P, vector<P>, greater<P>> pq;
    
    distanceTo[startNode] = 0;
    pq.push({0, startNode});
    
    while (!pq.empty()) {
        auto [dist, node] = pq.top(); pq.pop();
        if (visited[node]) continue;
        visited[node] = true;
        
        for (int i = 0; i < adj[node].size(); ++i) {
            int neighbor = adj[node][i];
            ll edgeWeight = weights[node][i];
            if (distanceTo[neighbor] > dist + edgeWeight) {
                distanceTo[neighbor] = dist + edgeWeight;
                pq.push({distanceTo[neighbor], neighbor});
            }
        }
    }
}

int main() {
    cin >> nodeCount >> edgeCount >> startNode;
    
    for (int i = 0; i < edgeCount; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(v);
        weights[u].push_back(w);
    }
    
    dijkstra();
    
    for (int i = 1; i <= nodeCount; ++i) {
        if (distanceTo[i] < INF)
            cout << distanceTo[i] << " ";
        else
            cout << 2147483647 << " ";
    }
    cout << endl;
    return 0;
}

SPFA Algorithm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<int> adj[MAXN], weights[MAXN];
ll distanceTo[MAXN];
bool inQueue[MAXN];
int startNode, nodeCount, edgeCount;

void spfa() {
    fill(distanceTo, distanceTo + nodeCount + 1, INF);
    queue<int> q;
    
    distanceTo[startNode] = 0;
    inQueue[startNode] = true;
    q.push(startNode);
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        inQueue[current] = false;
        
        for (int i = 0; i < adj[current].size(); ++i) {
            int neighbor = adj[current][i];
            ll edgeWeight = weights[current][i];
            
            if (distanceTo[current] + edgeWeight < distanceTo[neighbor]) {
                distanceTo[neighbor] = distanceTo[current] + edgeWeight;
                if (!inQueue[neighbor]) {
                    inQueue[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }
}

int main() {
    cin >> nodeCount >> edgeCount >> startNode;
    
    for (int i = 0; i < edgeCount; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(v);
        weights[u].push_back(w);
    }
    
    spfa();
    
    for (int i = 1; i <= nodeCount; ++i) {
        if (distanceTo[i] < INF)
            cout << distanceTo[i] << " ";
        else
            cout << 2147483647 << " ";
    }
    cout << endl;
    return 0;
}

SPFA for Negative Cycle Detection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Edge { int to, weight, next; };
Edge edges[MAXN];
int head[MAXN], edgeCount = -1;
ll distanceTo[MAXN];
int visitCount[MAXN];
bool inQueue[MAXN];
int nodeCount, edgeQueryCount;

void addEdge(int from, int to, int weight) {
    edges[++edgeCount] = {to, weight, head[from]};
    head[from] = edgeCount;
}

void detectNegativeCycle() {
    fill(distanceTo + 1, distanceTo + nodeCount + 1, INF);
    memset(visitCount, 0, sizeof(visitCount));
    memset(inQueue, 0, sizeof(inQueue));
    queue<int> q;
    
    distanceTo[1] = 0;
    inQueue[1] = true;
    q.push(1);
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        inQueue[current] = false;
        
        for (int i = head[current]; i != -1; i = edges[i].next) {
            int neighbor = edges[i].to;
            int weight = edges[i].weight;
            
            if (distanceTo[current] + weight < distanceTo[neighbor]) {
                distanceTo[neighbor] = distanceTo[current] + weight;
                visitCount[neighbor] = visitCount[current] + 1;
                
                if (visitCount[neighbor] >= nodeCount) {
                    cout << "YES" << endl;
                    return;
                }
                
                if (!inQueue[neighbor]) {
                    inQueue[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }
    cout << "NO" << endl;
}

int main() {
    int testCase;
    cin >> testCase;
    
    while (testCase--) {
        edgeCount = -1;
        memset(head, -1, sizeof(head));
        cin >> nodeCount >> edgeQueryCount;
        
        for (int i = 0; i < edgeQueryCount; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            addEdge(u, v, w);
            if (w >= 0) addEdge(v, u, w);
        }
        
        detectNegativeCycle();
    }
    return 0;
}

Difference Constraints System

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1000010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Constraint { int to, next, weight; };
Constraint constraints[MAXN];
int head[MAXN], constraintCount = 0;
ll distanceTo[MAXN];
int visitCount[MAXN];
bool inQueue[MAXN];
int variableCount, constraintNum;

void addConstraint(int from, int to, int diff) {
    constraints[++constraintCount] = {to, head[from], diff};
    head[from] = constraintCount;
}

void solveConstraints() {
    fill(distanceTo + 1, distanceTo + variableCount + 2, INF);
    queue<int> q;
    
    distanceTo[variableCount + 1] = 0;
    inQueue[variableCount + 1] = true;
    q.push(variableCount + 1);
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        inQueue[current] = false;
        
        for (int i = head[current]; i; i = constraints[i].next) {
            int neighbor = constraints[i].to;
            int weight = constraints[i].weight;
            
            if (distanceTo[current] + weight < distanceTo[neighbor]) {
                distanceTo[neighbor] = distanceTo[current] + weight;
                visitCount[neighbor] = visitCount[current] + 1;
                
                if (visitCount[neighbor] >= variableCount) {
                    cout << "NO SOLUTION" << endl;
                    exit(0);
                }
                
                if (!inQueue[neighbor]) {
                    inQueue[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }
}

int main() {
    cin >> variableCount >> constraintNum;
    
    for (int i = 0; i < constraintNum; ++i) {
        int x, y, bound;
        cin >> x >> y >> bound;
        addConstraint(y, x, bound); // Represents x - y >= -bound
    }
    
    for (int i = 1; i <= variableCount; ++i)
        addConstraint(variableCount + 1, i, 0);
        
    solveConstraints();
    
    ll minValue = INF;
    for (int i = 1; i <= variableCount; ++i)
        minValue = min(minValue, distanceTo[i]);
        
    for (int i = 1; i <= variableCount; ++i)
        cout << distanceTo[i] - minValue << endl;
        
    return 0;
}

Minimum Spanning Tree

Kruskal's Algorithm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 5010, MAXM = 400010;

struct Edge { int u, v, weight; };
Edge edges[MAXM];
int parent[MAXN];
ll totalWeight = 0;
int nodeCount, edgeCount, connectedComponents = 0;

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

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

void unionSets(int x, int y) {
    int rootX = findRoot(x), rootY = findRoot(y);
    if (rootX != rootY) parent[rootX] = rootY;
}

bool isConnected(int x, int y) {
    return findRoot(x) == findRoot(y);
}

void kruskal() {
    sort(edges + 1, edges + edgeCount + 1, compareEdges);
    
    for (int i = 1; i <= edgeCount; ++i) {
        int u = edges[i].u, v = edges[i].v;
        if (isConnected(u, v)) continue;
        
        unionSets(u, v);
        totalWeight += edges[i].weight;
        if (++connectedComponents == nodeCount - 1) break;
    }
}

int main() {
    cin >> nodeCount >> edgeCount;
    iota(parent + 1, parent + nodeCount + 1, 1);
    
    for (int i = 1; i <= edgeCount; ++i)
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        
    kruskal();
    
    if (connectedComponents == nodeCount - 1)
        cout << totalWeight << endl;
    else
        cout << "orz" << endl;
        
    return 0;
}

Prim's Algorithm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 5010;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll xCoord[MAXN], yCoord[MAXN], minDist[MAXN];
bool visited[MAXN];
int nodeCount, minCost;

ll squaredDistance(int a, int b) {
    ll dx = xCoord[a] - xCoord[b];
    ll dy = yCoord[a] - yCoord[b];
    return dx * dx + dy * dy;
}

void prim() {
    fill(minDist, minDist + nodeCount + 1, INF);
    minDist[1] = 0;
    
    for (int iteration = 1; iteration <= nodeCount; ++iteration) {
        int closestNode = 0;
        for (int i = 1; i <= nodeCount; ++i) {
            if (!visited[i] && minDist[i] < minDist[closestNode])
                closestNode = i;
        }
        
        if (closestNode == 0 || minDist[closestNode] == INF) {
            cout << -1 << endl;
            exit(0);
        }
        
        visited[closestNode] = true;
        
        for (int j = 1; j <= nodeCount; ++j) {
            if (!visited[j] && j != closestNode) {
                ll dist = squaredDistance(j, closestNode);
                if (dist >= minCost)
                    minDist[j] = min(minDist[j], dist);
            }
        }
    }
}

int main() {
    cin >> nodeCount >> minCost;
    
    for (int i = 1; i <= nodeCount; ++i)
        cin >> xCoord[i] >> yCoord[i];
        
    prim();
    
    ll result = 0;
    for (int i = 1; i <= nodeCount; ++i) {
        if (minDist[i] == INF) {
            cout << -1 << endl;
            return 0;
        }
        result += minDist[i];
    }
    
    cout << result << endl;
    return 0;
}

Topological Sorting

Basic Topological Sort

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 30010, MAXE = 1000010;

struct Edge { int next, to; };
Edge edges[MAXE];
int head[MAXN], inDegree[MAXN], resultOrder[MAXN];
int edgeCount = 0, nodeCount, sortedCount = 0;

void addEdge(int from, int to) {
    edges[++edgeCount] = {head[from], to};
    head[from] = edgeCount;
}

void topologicalSort() {
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int i = 1; i <= nodeCount; ++i) {
        if (inDegree[i] == 0)
            pq.push(i);
    }
    
    while (!pq.empty()) {
        int current = pq.top(); pq.pop();
        resultOrder[++sortedCount] = current;
        
        for (int i = head[current]; i; i = edges[i].next) {
            int neighbor = edges[i].to;
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0)
                pq.push(neighbor);
        }
    }
}

int main() {
    cin >> nodeCount;
    
    for (int i = 1; i <= nodeCount; ++i) {
        int dependencyCount;
        cin >> dependencyCount;
        
        for (int j = 0; j < dependencyCount; ++j) {
            int dependent;
            cin >> dependent;
            addEdge(i, dependent);
            inDegree[dependent]++;
        }
    }
    
    topologicalSort();
    
    if (sortedCount != nodeCount)
        cout << "no solution" << endl;
    else {
        cout << nodeCount << endl;
        for (int i = 1; i <= nodeCount; ++i)
            cout << resultOrder[i] << " ";
        cout << endl;
    }
    return 0;
}

Strongly Connected Components

Tarjan's Algorithm to SCC

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 10010, MAXE = 50010;

struct Edge { int to, next; };
Edge edges[MAXE];
int head[MAXN], edgeCount = 0;
int discoveryTime[MAXN], lowLink[MAXN], componentId[MAXN];
int timeCounter = 0, componentCount = 0, sccWithMultipleNodes = 0;
bool inStack[MAXN];
stack<int> nodeStack;
int nodeCount, edgeCountInput;

void addEdge(int from, int to) {
    edges[++edgeCount] = {to, head[from]};
    head[from] = edgeCount;
}

void tarjan(int node) {
    discoveryTime[node] = lowLink[node] = ++timeCounter;
    nodeStack.push(node);
    inStack[node] = true;
    
    for (int i = head[node]; i; i = edges[i].next) {
        int neighbor = edges[i].to;
        if (!discoveryTime[neighbor]) {
            tarjan(neighbor);
            lowLink[node] = min(lowLink[node], lowLink[neighbor]);
        } else if (inStack[neighbor]) {
            lowLink[node] = min(lowLink[node], discoveryTime[neighbor]);
        }
    }
    
    if (lowLink[node] == discoveryTime[node]) {
        int componentSize = 0, current;
        componentCount++;
        
        do {
            current = nodeStack.top(); nodeStack.pop();
            componentId[current] = componentCount;
            componentSize++;
            inStack[current] = false;
        } while (current != node);
        
        if (componentSize > 1)
            sccWithMultipleNodes++;
    }
}

int main() {
    cin >> nodeCount >> edgeCountInput;
    
    for (int i = 0; i < edgeCountInput; ++i) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }
    
    for (int i = 1; i <= nodeCount; ++i) {
        if (!discoveryTime[i])
            tarjan(i);
    }
    
    cout << sccWithMultipleNodes << endl;
    return 0;
}

Prime Number Testing

Fermat Primality Test

#include <random>
mt19937 rng(time(0));

int randomInRange(int low, int high) {
    uniform_int_distribution<int> dist(low, high);
    return dist(rng);
}

ll modularPower(ll base, ll exp, ll mod) {
    ll result = 1;
    while (exp) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

bool isProbablyPrime(ll n) {
    if (n < 3) return n == 2;
    
    for (int test = 0; test < 12; ++test) {
        ll a = randomInRange(2, n - 1);
        if (modularPower(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

Miller-Rabin Primality Test

typedef long long ll;

ll safeMultiply(ll a, ll b, ll mod) {
    return (__int128)a * b % mod;
}

ll modularPower(ll base, ll exp, ll mod) {
    ll result = 1;
    while (exp) {
        if (exp & 1) result = safeMultiply(result, base, mod);
        base = safeMultiply(base, base, mod);
        exp >>= 1;
    }
    return result;
}

bool isPrime(ll n) {
    if (n < 3) return n == 2;
    if (n % 2 == 0) return false;
    
    static const ll witnesses[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    ll d = n - 1, r = 0;
    
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }
    
    for (ll a : witnesses) {
        if (a >= n) break;
        ll x = modularPower(a, d, n);
        if (x <= 1 || x == n - 1) continue;
        
        bool composite = true;
        for (int i = 0; i < r; ++i) {
            x = safeMultiply(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
            if (x == 1) return false;
        }
        if (composite) return false;
    }
    return true;
}

Fast I/O Utilities

Template-Based Fast Input

template <typename T>
void read(T &value) {
    char ch = getchar();
    int sign = 1;
    value = 0;
    
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    
    while (ch >= '0' && ch <= '9') {
        value = value * 10 + (ch - '0');
        ch = getchar();
    }
    
    value *= sign;
}

Gaussain Elimination

Basic Linear System Solver

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 111;
const double EPS = 1e-7;

double matrix[MAXN][MAXN], solution[MAXN];
int equationCount;

int main() {
    cin >> equationCount;
    
    for (int i = 1; i <= equationCount; ++i)
        for (int j = 1; j <= equationCount + 1; ++j)
            scanf("%lf", &matrix[i][j]);
            
    for (int col = 1; col <= equationCount; ++col) {
        int pivotRow = col;
        for (int row = col + 1; row <= equationCount; ++row) {
            if (fabs(matrix[row][col]) > fabs(matrix[pivotRow][col]))
                pivotRow = row;
        }
        
        if (fabs(matrix[pivotRow][col]) < EPS) {
            printf("No Solution");
            return 0;
        }
        
        if (pivotRow != col)
            swap(matrix[col], matrix[pivotRow]);
            
        double divisor = matrix[col][col];
        for (int j = col; j <= equationCount + 1; ++j)
            matrix[col][j] /= divisor;
            
        for (int row = col + 1; row <= equationCount; ++row) {
            double factor = matrix[row][col];
            for (int j = col; j <= equationCount + 1; ++j)
                matrix[row][j] -= matrix[col][j] * factor;
        }
    }
    
    solution[equationCount] = matrix[equationCount][equationCount + 1];
    for (int i = equationCount - 1; i >= 1; --i) {
        solution[i] = matrix[i][equationCount + 1];
        for (int j = i + 1; j <= equationCount; ++j)
            solution[i] -= matrix[i][j] * solution[j];
    }
    
    for (int i = 1; i <= equationCount; ++i)
        printf("%.2lf\n", solution[i]);
        
    return 0;
}