Basic Math

Master fundamental mathematical concepts essential for algorithmic problem solving.

Prime Numbers

Prime Number Properties

• Definition: Natural number greater than 1 with no positive divisors other than 1 and itself
• First few primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...

Prime Checking

// Check if a number is prime
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

Sieve of Eratosthenes

// Generate all primes up to n
vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

Prime Factorization

// Get prime factors of a number
vector<pair<int, int>> primeFactors(int n) {
    vector<pair<int, int>> factors;
    
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            factors.push_back({i, count});
        }
    }
    
    if (n > 1) {
        factors.push_back({n, 1});
    }
    
    return factors;
}

GCD & LCM

Greatest Common Divisor (GCD)

// Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Recursive version
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

Least Common Multiple (LCM)

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

Extended Euclidean Algorithm

// Find x, y such that ax + by = gcd(a, b)
int extendedGcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1;
    int g = extendedGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

Modular Arithmetic

Modular Addition

// (a + b) mod m
int modAdd(int a, int b, int m) {
    return ((a % m) + (b % m)) % m;
}

Modular Multiplication

// (a * b) mod m
int modMul(int a, int b, int m) {
    return ((a % m) * (b % m)) % m;
}

Modular Exponentiation

// (a^b) mod m
int modPow(int base, int exp, int mod) {
    int result = 1;
    base %= mod;
    
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    
    return result;
}

Modular Inverse

// Find x such that (a * x) ≡ 1 (mod m)
int modInverse(int a, int m) {
    int x, y;
    int g = extendedGcd(a, m, x, y);
    
    if (g != 1) {
        return -1; // No inverse exists
    }
    
    return (x % m + m) % m;
}

Factorial & Permutations

Factorial

// Calculate n!
long long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Factorial with modulo
int factorialMod(int n, int mod) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result = (result * i) % mod;
    }
    return result;
}

Permutations

// Calculate P(n, r) = n! / (n-r)!
long long permutation(int n, int r) {
    if (r > n) return 0;
    
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result *= (n - i);
    }
    return result;
}

Combinations

// Calculate C(n, r) = n! / (r! * (n-r)!)
long long combination(int n, int r) {
    if (r > n) return 0;
    if (r > n - r) r = n - r; // Optimization
    
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

Combinatorics

Pascal's Triangle

// Generate Pascal's triangle
vector<vector<int>> pascalTriangle(int n) {
    vector<vector<int>> triangle(n);
    
    for (int i = 0; i < n; i++) {
        triangle[i].resize(i + 1);
        triangle[i][0] = triangle[i][i] = 1;
        
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    
    return triangle;
}

Catalan Numbers

// Calculate nth Catalan number
long long catalan(int n) {
    if (n <= 1) return 1;
    
    long long result = 0;
    for (int i = 0; i < n; i++) {
        result += catalan(i) * catalan(n - 1 - i);
    }
    return result;
}

// Dynamic programming approach
long long catalanDP(int n) {
    vector<long long> dp(n + 1, 0);
    dp[0] = dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    
    return dp[n];
}

Fibonacci Numbers

// Calculate nth Fibonacci number
long long fibonacci(int n) {
    if (n <= 1) return n;
    
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Number Theory Concepts

Divisors

// Get all divisors of a number
vector<int> getDivisors(int n) {
    vector<int> divisors;
    
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i != n / i) {
                divisors.push_back(n / i);
            }
        }
    }
    
    sort(divisors.begin(), divisors.end());
    return divisors;
}

Totient Function (Euler's Phi)

// Calculate φ(n) - count of numbers coprime to n
int eulerPhi(int n) {
    int result = n;
    
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i;
        }
    }
    
    if (n > 1) {
        result -= result / n;
    }
    
    return result;
}

Common Patterns

1. Prime factorization for divisor problems
2. GCD/LCM for fraction and multiple problems
3. Modular arithmetic for large number calculations
4. Combinatorics for counting problems
5. Number theory for mathematical properties

Performance Tips

• Use sieve for multiple prime checks
• Precompute factorials for combination problems
• Use modular arithmetic to prevent overflow
• Optimize GCD with binary GCD algorithm
• Cache results for expensive calculations