Number Theory for Competitive Programming

Number theory provides essential tools for competitive programming, including GCD/LCM calculations, modular arithmetic, prime numbers, and Euler's theorem. These concepts appear frequently in contest problems and form the foundation for advanced algorithms.

GCD and LCM

The greatest common divisor (GCD) and least common multiple (LCM) are fundamental operations in number theory with many applications.

GCD and LCM Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class NumberTheory {
public:
    // Euclidean algorithm for GCD
    static long long gcd(long long a, long long b) {
        while (b != 0) {
            long long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // LCM using GCD
    static long long lcm(long long a, long long b) {
        return (a / gcd(a, b)) * b; // avoid overflow
    }
    
    // Extended Euclidean Algorithm
    static long long extendedGCD(long long a, long long b, long long& x, long long& y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        
        long long x1, y1;
        long long gcd_val = extendedGCD(b, a % b, x1, y1);
        
        x = y1;
        y = x1 - (a / b) * y1;
        
        return gcd_val;
    }
    
    // Modular multiplicative inverse
    static long long modInverse(long long a, long long m) {
        long long x, y;
        long long g = extendedGCD(a, m, x, y);
        
        if (g != 1) {
            return -1; // inverse does not exist
        }
        
        return (x % m + m) % m;
    }
    
    // Fast exponentiation with modulo
    static long long powerMod(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;
    }
    
    // GCD of array
    static long long arrayGCD(vector<long long>& arr) {
        long long result = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            result = gcd(result, arr[i]);
            if (result == 1) break; // optimization
        }
        return result;
    }
    
    // LCM of array
    static long long arrayLCM(vector<long long>& arr) {
        long long result = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            result = lcm(result, arr[i]);
        }
        return result;
    }
};

int main() {
    // Test basic GCD and LCM
    long long a = 48, b = 18;
    cout << "Numbers: " << a << ", " << b << endl;
    cout << "GCD: " << NumberTheory::gcd(a, b) << endl;
    cout << "LCM: " << NumberTheory::lcm(a, b) << endl;
    
    // Test extended GCD
    long long x, y;
    long long g = NumberTheory::extendedGCD(a, b, x, y);
    cout << "\nExtended GCD: " << g << endl;
    cout << "Coefficients: x=" << x << ", y=" << y << endl;
    cout << "Verification: " << a << "*" << x << " + " << b << "*" << y << " = " << (a*x + b*y) << endl;
    
    // Test modular inverse
    long long num = 3, mod = 11;
    long long inv = NumberTheory::modInverse(num, mod);
    cout << "\nModular inverse of " << num << " mod " << mod << ": " << inv << endl;
    if (inv != -1) {
        cout << "Verification: " << num << "*" << inv << " ≡ " << (num * inv) % mod << " (mod " << mod << ")" << endl;
    }
    
    // Test fast exponentiation
    long long base = 2, exp = 10, modulo = 1000000007;
    long long power = NumberTheory::powerMod(base, exp, modulo);
    cout << "\n" << base << "^" << exp << " mod " << modulo << " = " << power << endl;
    
    // Test array operations
    vector<long long> arr = {12, 18, 24, 36};
    cout << "\nArray: ";
    for (long long x : arr) cout << x << " ";
    cout << endl;
    cout << "Array GCD: " << NumberTheory::arrayGCD(arr) << endl;
    cout << "Array LCM: " << NumberTheory::arrayLCM(arr) << endl;
    
    return 0;
}

These fundamental number theory operations use efficient algorithms: Euclidean algorithm for GCD (O(log min(a,b))), extended GCD for finding coefficients, and fast exponentiation for modular arithmetic (O(log n)).

Prime Numbers and Factorization

Prime number algorithms are essential for many competitive programming problems, including factorization and primality testing.

Prime Numbers and Factorization

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;

class PrimeUtils {
public:
    // Sieve of Eratosthenes
    static vector<bool> sieveOfEratosthenes(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;
    }
    
    // Get all primes up to n
    static vector<int> getPrimes(int n) {
        vector<bool> isPrime = sieveOfEratosthenes(n);
        vector<int> primes;
        
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.push_back(i);
            }
        }
        
        return primes;
    }
    
    // Check if number is prime (for large numbers)
    static bool isPrime(long long n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (long long i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        
        return true;
    }
    
    // Prime factorization
    static map<long long, int> primeFactorization(long long n) {
        map<long long, int> factors;
        
        // Handle factor of 2
        while (n % 2 == 0) {
            factors[2]++;
            n /= 2;
        }
        
        // Handle odd factors
        for (long long i = 3; i * i <= n; i += 2) {
            while (n % i == 0) {
                factors[i]++;
                n /= i;
            }
        }
        
        // If n is still > 1, then it is prime
        if (n > 1) {
            factors[n]++;
        }
        
        return factors;
    }
    
    // Count divisors using prime factorization
    static long long countDivisors(long long n) {
        map<long long, int> factors = primeFactorization(n);
        long long count = 1;
        
        for (auto& [prime, power] : factors) {
            count *= (power + 1);
        }
        
        return count;
    }
    
    // Sum of divisors using prime factorization
    static long long sumOfDivisors(long long n) {
        map<long long, int> factors = primeFactorization(n);
        long long sum = 1;
        
        for (auto& [prime, power] : factors) {
            long long termSum = 0;
            long long primePower = 1;
            
            for (int i = 0; i <= power; i++) {
                termSum += primePower;
                primePower *= prime;
            }
            
            sum *= termSum;
        }
        
        return sum;
    }
    
    // Euler's totient function
    static long long eulerTotient(long long n) {
        map<long long, int> factors = primeFactorization(n);
        long long result = n;
        
        for (auto& [prime, power] : factors) {
            result = result / prime * (prime - 1);
        }
        
        return result;
    }
};

int main() {
    int n = 30;
    
    // Generate primes up to n
    vector<int> primes = PrimeUtils::getPrimes(n);
    cout << "Primes up to " << n << ": ";
    for (int p : primes) cout << p << " ";
    cout << endl;
    
    // Test prime checking
    vector<long long> testNumbers = {17, 25, 97, 100};
    cout << "\nPrime checking:" << endl;
    for (long long num : testNumbers) {
        cout << num << ": " << (PrimeUtils::isPrime(num) ? "Prime" : "Not prime") << endl;
    }
    
    // Test factorization
    long long factorNum = 60;
    cout << "\nPrime factorization of " << factorNum << ": ";
    map<long long, int> factors = PrimeUtils::primeFactorization(factorNum);
    bool first = true;
    for (auto& [prime, power] : factors) {
        if (!first) cout << " × ";
        cout << prime;
        if (power > 1) cout << "^" << power;
        first = false;
    }
    cout << endl;
    
    // Test divisor functions
    cout << "Number of divisors: " << PrimeUtils::countDivisors(factorNum) << endl;
    cout << "Sum of divisors: " << PrimeUtils::sumOfDivisors(factorNum) << endl;
    cout << "Euler totient: " << PrimeUtils::eulerTotient(factorNum) << endl;
    
    return 0;
}

Prime algorithms use optimized approaches: sieve for multiple queries O(n log log n), trial division with 6k±1 optimization, and efficient factorization for computing number-theoretic functions.

Key Takeaways

Euclidean algorithm provides efficient GCD computation in O(log min(a,b)) time
Extended GCD enables modular inverse computation and solving linear Diophantine equations
Sieve of Eratosthenes efficiently finds all primes up to n in O(n log log n) time
Prime factorization enables computation of divisor functions and number-theoretic properties