← All patterns

Math & Geometry

Number theory (GCD, modular arithmetic, primes), big-number arithmetic on strings, coordinate geometry, area and orientation tests, and modular exponentiation.

37 problems 14 Easy 14 Medium 9 Hard

Number theory (GCD, primes, modular arithmetic), big-number arithmetic on strings, coordinate geometry (orientation, area, distance), modular exponentiation, fast exponentiation by squaring. Many problems reduce to a few canonical identities — Bezout for water-and-jug, modular inverse for division-under-mod, cross product for orientation.

For competition-grade problems, modular arithmetic with prime moduli is the workhorse.

When to reach for this pattern

  • Modular arithmetic with large powers — use fast exponentiation
  • GCD / LCM relations between values
  • Geometric: line, polygon area, point-in-shape, collinearity
  • Big numbers exceeding 64-bit — string arithmetic

Canonical template 

// fast modular exponentiation
long long modpow(long long b, long long e, long long m) {
    long long r = 1; b %= m;
    while (e) {
        if (e & 1) r = r * b % m;
        b = b * b % m;
        e >>= 1;
    }
    return r;
}

// GCD
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

// cross product for orientation
long long cross(long long ox, long long oy, long long ax, long long ay, long long bx, long long by) {
    return (ax - ox) * (by - oy) - (ay - oy) * (bx - ox);
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • Modular inverse needs Fermat's little theorem (modpow(x, MOD - 2, MOD)) when MOD is prime, or extended Euclidean otherwise
  • Integer overflow on intermediate products — cast to long long before multiplying
  • Floating-point geometry: use cross products in integer arithmetic where possible
  • Negative remainders in C++ %: normalize with ((x % m) + m) % m

Related patterns

Bitwise Operations Dynamic Programming

Problems (37)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.