1 GCD / LCM (Euclid)

while b != 0:  (a, b) = (b, a mod b)
gcd = a;   lcm = a / gcd * b     // divide first!

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

function gcd(a, b) {
  while (b !== 0n && b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

2 Sieve of Eratosthenes

mark all true;  for p = 2 while p*p <= n:
    if prime[p]: cross p*p, p*p+p, ...

Time: O(n log log n). Start crossing at p*p — smaller multiples are already crossed.

3 Modular Rules

(a + b) % m = (a%m + b%m) % m
(a * b) % m = (a%m * b%m) % m
a / b mod p = a * inverse(b) mod p      // p prime → inv(b) = b^(p-2)

Multiply in long/i64/BigInt — (10^9)^2 overflows 32-bit.

4 Fast Power

result = 1
while exp > 0:
    if exp is odd: result *= base
    base *= base;  exp >>= 1

Time: O(log exp).

5 nCr mod p

precompute fact[0..n], inv[i] = fast_pow(fact[i], p-2, p)
C(n, r) = fact[n] * inv[r] * inv[n-r]

Small n (< ~1000)? Pascal’s triangle needs no inverses.