Integer Summation and Overflow Prevention

The formula for the sum of the first n natural numbers is SUM = n * (n + 1) / 2. However, performing multiplication before division may cause integer overflow even if the final result fits within the data type.

Mitigation strategies:

1. Use a 64-bit integer type such as long long.
2. Rearrange the computation to divide first: (n / 2) * (n + 1) or n * ((n + 1) / 2), depending on parity.

Least Common Multiple (LCM) via GCD

The greatest common divisor (GCD) can be efficiently computed using the Euclidean algorithm, wich repeatedly replaces the larger number by its remainder modulo the smaller one.

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Once GCD is known, LCM is derived as:

LCM(a, b) = (a / gcd(a, b)) * b;

Note the division before multiplication to avoid overflow.

Extracting the Last Digit of Large Powers

The last digit of powers of any integer repeats in cycles. Due to the pigeonhole principle and properties of modular arithmetic modulo 10, the cycle length is at most 4 for coprime bases, and generally short.

Example: The last digits of powers of 3 follow 3, 9, 7, 1, and then repeat. Thus, compute n mod 4 (with adjustment for zero) to determine the position in the cycle.

Fast Exponentiation (Exponentiation by Squaring)

This technique reduces time complexity from O(n) to O(log n) by leveraging binary representation of the exponent.

Iterative version (preferred for stack safety):

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

Modular reduction is typically applied at each step to prevent overflow and meet problem constraints.

Binary Search

Binary search halves the search space each iteration and requires monotonicity—either a sorted array or a monotonic function.

Iterative implementation:

int binary_search(int arr[], int size, int target) {
    int lo = 0, hi = size - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoids overflow
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

Ternary Search for Unimodal Functions

Ternary search locates the extremum (maximum or minimum) of a unimodal function—e.g., convex or concave—over an interval without requiring derviatives.

Two interior points divide the interval into thirds:

double l = left, r = right;
while (r - l > 1e-9) {
    double m1 = l + (r - l) / 3.0;
    double m2 = r - (r - l) / 3.0;
    if (f(m1) < f(m2))
        l = m1;   // for maximum; reverse for minimum
    else
        r = m2;
}

This method converges logarithmically and is useful in optimization problems with single extrema.