Number Theory

Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Primality Testing

bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    // Check for divisors from 5 to sqrt(n)
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

Sieve of Eratosthenes

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

// Get list of primes up to n
vector<int> getPrimes(int n) {
    vector<bool> is_prime = sieve(n);
    vector<int> primes;
    
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

Sieve Optimization:

Time complexity: O(n log log n). Space: O(n). For n ≤ 10^7, sieve is very efficient.

Prime Factorization

Trial Division Method

vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> factors; // {prime, power}
    
    // Check for factor 2
    if (n % 2 == 0) {
        int power = 0;
        while (n % 2 == 0) {
            n /= 2;
            power++;
        }
        factors.push_back({2, power});
    }
    
    // Check for odd factors
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            int power = 0;
            while (n % i == 0) {
                n /= i;
                power++;
            }
            factors.push_back({i, power});
        }
    }
    
    // If n is still > 1, then it's a prime
    if (n > 1) {
        factors.push_back({n, 1});
    }
    
    return factors;
}

Factorization using Precomputed Primes

vector<int> primes; // Precomputed primes

vector<pair<int, int>> fastFactorize(long long n) {
    vector<pair<int, int>> factors;
    
    for (int p : primes) {
        if ((long long)p * p > n) break;
        
        if (n % p == 0) {
            int power = 0;
            while (n % p == 0) {
                n /= p;
                power++;
            }
            factors.push_back({p, power});
        }
    }
    
    if (n > 1) {
        factors.push_back({(int)n, 1});
    }
    
    return factors;
}

GCD and LCM

Euclidean Algorithm for GCD

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

// Iterative GCD
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

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

Extended Euclidean Algorithm

// Returns gcd(a, b) and finds 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 gcd = extendedGCD(b, a % b, x1, y1);
    
    x = y1;
    y = x1 - (a / b) * y1;
    
    return gcd;
}

Properties:

gcd(a, b) = gcd(b, a % b)
lcm(a, b) = a * b / gcd(a, b)
gcd(a, b) * lcm(a, b) = a * b
gcd(a, 0) = a

Modular Arithmetic

Basic Operations

const int MOD = 1e9 + 7;

// Safe modular addition
int addMod(int a, int b) {
    return ((a % MOD) + (b % MOD)) % MOD;
}

// Safe modular subtraction
int subMod(int a, int b) {
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

// Safe modular multiplication
long long mulMod(long long a, long long b) {
    return ((a % MOD) * (b % MOD)) % MOD;
}

Fast Modular Exponentiation

long long fastPower(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;
}

// Alternative using bit manipulation
long long power(long long a, long long b, long long m = MOD) {
    long long res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

Modular Inverse

Using Fermat's Little Theorem

If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p), so a^(p-2) ≡ a^(-1) (mod p)

long long modInverse(long long a, long long p) {
    // Only works when p is prime
    return fastPower(a, p - 2, p);
}

// Modular division: (a / b) mod p = (a * b^(-1)) mod p
long long modDivision(long long a, long long b, long long p) {
    return (a * modInverse(b, p)) % p;
}

Using Extended Euclidean Algorithm

long long modInverseExt(long long a, long long m) {
    int x, y;
    int g = extendedGCD(a, m, x, y);
    
    if (g != 1) {
        return -1; // Inverse doesn't exist
    }
    
    return (x % m + m) % m;
}

Euler's Totient Function

φ(n) counts the positive integers up to n that are coprime to n.

// Calculate φ(n) for single number
int phi(int n) {
    int result = n;
    
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            // Remove all factors of p
            while (n % p == 0) {
                n /= p;
            }
            // Multiply result by (1 - 1/p)
            result -= result / p;
        }
    }
    
    // If n has a prime factor greater than sqrt(n)
    if (n > 1) {
        result -= result / n;
    }
    
    return result;
}

// Compute φ(i) for all i from 1 to n using sieve
vector<int> phiSieve(int n) {
    vector<int> phi(n + 1);
    
    // Initialize phi[i] = i
    for (int i = 1; i <= n; i++) {
        phi[i] = i;
    }
    
    // Apply Euler's formula
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) { // i is prime
            for (int j = i; j <= n; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
    
    return phi;
}

Euler's Theorem:

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n)

This generalizes Fermat's Little Theorem.

Chinese Remainder Theorem

Solves system of congruences: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ)

// Solve x ≡ a (mod m) and x ≡ b (mod n) where gcd(m, n) = 1
long long crt(long long a, long long m, long long b, long long n) {
    int x, y;
    int g = extendedGCD(m, n, x, y);
    
    if (g != 1) {
        return -1; // No solution if m and n are not coprime
    }
    
    long long result = ((a * n % (m * n)) * y % (m * n) + 
                       (b * m % (m * n)) * x % (m * n)) % (m * n);
    
    return (result + m * n) % (m * n);
}

// General CRT for multiple congruences
pair<long long, long long> crtGeneral(vector<long long> a, vector<long long> m) {
    int n = a.size();
    long long a1 = a[0], m1 = m[0];
    
    for (int i = 1; i < n; i++) {
        long long a2 = a[i], m2 = m[i];
        int x, y;
        long long g = extendedGCD(m1, m2, x, y);
        
        if ((a2 - a1) % g != 0) {
            return {-1, -1}; // No solution
        }
        
        long long lcm = m1 / g * m2;
        a1 = ((a1 + m1 * ((a2 - a1) / g) % (lcm / m1) * x) % lcm + lcm) % lcm;
        m1 = lcm;
    }
    
    return {a1, m1}; // x ≡ a1 (mod m1)
}

Linear Diophantine Equations

Equation of the form ax + by = c has integer solutions if and only if gcd(a, b) divides c.

bool solveDiophantine(int a, int b, int c, int& x, int& y) {
    int g = extendedGCD(abs(a), abs(b), x, y);
    
    if (c % g != 0) {
        return false; // No solution
    }
    
    // Scale the solution
    x *= c / g;
    y *= c / g;
    
    // Handle negative coefficients
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    
    return true;
}

// Find all solutions in a range
void findAllSolutions(int a, int b, int c, int minx, int maxx) {
    int x, y;
    if (!solveDiophantine(a, b, c, x, y)) {
        cout << "No solution" << endl;
        return;
    }
    
    int g = gcd(abs(a), abs(b));
    int dx = b / g;  // Step for x
    int dy = -a / g; // Step for y
    
    // Find the range of valid k values
    // x + k * dx should be in [minx, maxx]
    int k_min = (minx - x + dx - 1) / dx; // Ceiling division
    int k_max = (maxx - x) / dx;          // Floor division
    
    for (int k = k_min; k <= k_max; k++) {
        int sol_x = x + k * dx;
        int sol_y = y + k * dy;
        cout << "Solution: x = " << sol_x << ", y = " << sol_y << endl;
    }
}

Number Theory Applications

Counting Divisors

int countDivisors(int n) {
    int count = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i == n) {
                count++; // Perfect square
            } else {
                count += 2; // i and n/i are both divisors
            }
        }
    }
    return count;
}

// Using prime factorization: if n = p₁^a₁ * p₂^a₂ * ... * pₖ^aₖ
// then number of divisors = (a₁ + 1) * (a₂ + 1) * ... * (aₖ + 1)
int countDivisorsFromFactors(vector<pair<int, int>> factors) {
    int count = 1;
    for (auto [prime, power] : factors) {
        count *= (power + 1);
    }
    return count;
}

Sum of Divisors

long long sumDivisors(int n) {
    long long sum = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) {
                sum += n / i;
            }
        }
    }
    return sum;
}

// Using prime factorization: sum = ∏(pᵢ^(aᵢ+1) - 1)/(pᵢ - 1)
long long sumDivisorsFromFactors(vector<pair<int, int>> factors) {
    long long sum = 1;
    for (auto [p, a] : factors) {
        long long term = (fastPower(p, a + 1, MOD) - 1 + MOD) % MOD;
        term = (term * modInverse(p - 1, MOD)) % MOD;
        sum = (sum * term) % MOD;
    }
    return sum;
}

Practical Tips

Performance Tips:

Precompute primes using sieve for multiple queries
Use fast exponentiation for large powers
Cache results of expensive computations like φ(n)
Use long long to avoid overflow in intermediate calculations

Common Pitfalls:

Integer overflow in modular multiplication
Forgetting to take modulo in intermediate steps
Division by zero when computing modular inverse
Not checking if modular inverse exists

Key Formulas:

φ(p^k) = p^k - p^(k-1) for prime p
φ(mn) = φ(m)φ(n) if gcd(m,n) = 1
Σφ(d) = n for all divisors d of n
a^φ(n) ≡ 1 (mod n) if gcd(a,n) = 1

Prime Numbers

Primality Testing

Sieve of Eratosthenes

Sieve Optimization:

Prime Factorization

Trial Division Method

Factorization using Precomputed Primes

GCD and LCM

Euclidean Algorithm for GCD

Extended Euclidean Algorithm

Properties:

Modular Arithmetic

Basic Operations

Fast Modular Exponentiation

Modular Inverse

Using Fermat's Little Theorem

Using Extended Euclidean Algorithm

Euler's Totient Function

Euler's Theorem:

Chinese Remainder Theorem

Linear Diophantine Equations

Number Theory Applications

Counting Divisors

Sum of Divisors

Practical Tips

Performance Tips:

Common Pitfalls:

Key Formulas:

CodeForces Challenge Problems

Prime Numbers