🔢 Thuật toán toán học (Mathematical Algorithms)

📖 Giới thiệu

Mathematical algorithms là foundation của computer science, cung cấp efficient solutions cho number theory, combinatorics, và computational mathematics problems. Từ cryptography đến competitive programming, từ graphics đến machine learning, hiểu mathematical algorithms là essential cho bất kỳ developer nào.

Tại sao mathematical algorithms quan trọng?

Cryptography: RSA encryption, digital signatures
Computer Graphics: 3D transformations, collision detection
Game Development: Random generation, probability calculations
Data Science: Statistical analysis, sampling methods
Competitive Programming: Number theory problems, optimization

Core areas covered:

Number Theory: GCD, LCM, prime numbers, factorization
Modular Arithmetic: Fast exponentiation, modular inverse
Combinatorics: Permutations, combinations, Pascal's triangle
Probability: Random algorithms, Monte Carlo methods
Geometry: Computational geometry basics

Applications in tech:

Hash functions: Mathematical properties for distribution
Load balancing: Consistent hashing algorithms
Randomization: Shuffle algorithms, sampling
Optimization: Mathematical programming, linear algebra

🔧 Cú pháp

Number Theory Algorithms

cpp

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

class NumberTheory {
public:
    // Greatest Common Divisor (GCD) - Euclidean Algorithm
    long long gcd(long long a, long long b) {
        while (b != 0) {
            long long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // Extended Euclidean Algorithm
    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 = extendedGCD(b, a % b, x1, y1);
        
        x = y1;
        y = x1 - (a / b) * y1;
        
        return gcd;
    }
    
    // Least Common Multiple (LCM)
    long long lcm(long long a, long long b) {
        return (a / gcd(a, b)) * b;  // Avoid overflow
    }
    
    // Check if number is prime - Optimized trial division
    bool isPrime(long long n) {
        if (n <= 1) return false;
        if (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;
    }
    
    // Sieve of Eratosthenes - Generate all primes up to n
    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;
    }
    
    // Prime factorization
    vector<pair<long long, int>> primeFactorization(long long n) {
        vector<pair<long long, int>> factors;
        
        // Check for 2
        if (n % 2 == 0) {
            int count = 0;
            while (n % 2 == 0) {
                n /= 2;
                count++;
            }
            factors.push_back({2, count});
        }
        
        // Check for odd factors
        for (long long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                int count = 0;
                while (n % i == 0) {
                    n /= i;
                    count++;
                }
                factors.push_back({i, count});
            }
        }
        
        // If n is still > 1, it's a prime
        if (n > 1) {
            factors.push_back({n, 1});
        }
        
        return factors;
    }
    
    // Count divisors of a number
    long long countDivisors(long long n) {
        auto factors = primeFactorization(n);
        long long count = 1;
        
        for (auto& factor : factors) {
            count *= (factor.second + 1);
        }
        
        return count;
    }
    
    // Sum of divisors
    long long sumOfDivisors(long long n) {
        auto factors = primeFactorization(n);
        long long sum = 1;
        
        for (auto& factor : factors) {
            long long prime = factor.first;
            int power = factor.second;
            
            // Sum = (p^(k+1) - 1) / (p - 1)
            long long termSum = (pow(prime, power + 1) - 1) / (prime - 1);
            sum *= termSum;
        }
        
        return sum;
    }
};

Modular Arithmetic

cpp

class ModularArithmetic {
private:
    static const long long MOD = 1000000007;
    
public:
    // Fast exponentiation with modulo
    long long fastPower(long long base, long long exp, long long mod = 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;
    }
    
    // Modular inverse using Fermat's little theorem (when mod is prime)
    long long modInverse(long long a, long long mod = MOD) {
        return fastPower(a, mod - 2, mod);
    }
    
    // Modular inverse using Extended Euclidean Algorithm
    long long modInverseExtended(long long a, long long mod) {
        long long x, y;
        long long g = extendedGCD(a, mod, x, y);
        
        if (g != 1) {
            return -1;  // Inverse doesn't exist
        }
        
        return (x % mod + mod) % mod;
    }
    
    // Chinese Remainder Theorem
    long long chineseRemainderTheorem(vector<long long>& remainders, vector<long long>& moduli) {
        long long result = 0;
        long long product = 1;
        
        for (long long mod : moduli) {
            product *= mod;
        }
        
        for (int i = 0; i < remainders.size(); i++) {
            long long partialProduct = product / moduli[i];
            long long inverse = modInverseExtended(partialProduct, moduli[i]);
            result = (result + remainders[i] * partialProduct * inverse) % product;
        }
        
        return (result + product) % product;
    }
    
private:
    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 = extendedGCD(b, a % b, x1, y1);
        
        x = y1;
        y = x1 - (a / b) * y1;
        
        return gcd;
    }
};

Combinatorics

cpp

class Combinatorics {
private:
    static const long long MOD = 1000000007;
    vector<long long> factorial;
    vector<long long> invFactorial;
    
public:
    // Precompute factorials and inverse factorials
    void precompute(int maxN) {
        factorial.resize(maxN + 1);
        invFactorial.resize(maxN + 1);
        
        factorial[0] = 1;
        for (int i = 1; i <= maxN; i++) {
            factorial[i] = (factorial[i - 1] * i) % MOD;
        }
        
        invFactorial[maxN] = fastPower(factorial[maxN], MOD - 2);
        for (int i = maxN - 1; i >= 0; i--) {
            invFactorial[i] = (invFactorial[i + 1] * (i + 1)) % MOD;
        }
    }
    
    // nCr (Combinations) - Choose r items from n items
    long long nCr(int n, int r) {
        if (r > n || r < 0) return 0;
        if (r == 0 || r == n) return 1;
        
        return (factorial[n] * invFactorial[r] % MOD) * invFactorial[n - r] % MOD;
    }
    
    // nPr (Permutations) - Arrange r items from n items
    long long nPr(int n, int r) {
        if (r > n || r < 0) return 0;
        if (r == 0) return 1;
        
        return factorial[n] * invFactorial[n - r] % MOD;
    }
    
    // Derangements - Permutations with no element in original position
    long long derangements(int n) {
        if (n == 0) return 1;
        if (n == 1) return 0;
        if (n == 2) return 1;
        
        vector<long long> dp(n + 1);
        dp[0] = 1;
        dp[1] = 0;
        dp[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = ((long long)(i - 1) * (dp[i - 1] + dp[i - 2])) % MOD;
        }
        
        return dp[n];
    }
    
    // Catalan numbers - Count of valid parentheses sequences
    long long catalan(int n) {
        if (n <= 1) return 1;
        
        // C(n) = (2n)! / ((n+1)! * n!)
        long long result = factorial[2 * n];
        result = (result * invFactorial[n + 1]) % MOD;
        result = (result * invFactorial[n]) % MOD;
        
        return result;
    }
    
    // Stars and bars - Distribute n identical items into k groups
    long long starsAndBars(int n, int k) {
        return nCr(n + k - 1, k - 1);
    }
    
private:
    long long fastPower(long long base, long long exp) {
        long long result = 1;
        while (exp > 0) {
            if (exp & 1) result = (result * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }
};

Random Algorithms

cpp

class RandomAlgorithms {
private:
    mt19937 rng;
    
public:
    RandomAlgorithms() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
    
    // Fisher-Yates shuffle
    void shuffle(vector<int>& arr) {
        for (int i = arr.size() - 1; i > 0; i--) {
            uniform_int_distribution<int> dist(0, i);
            int j = dist(rng);
            swap(arr[i], arr[j]);
        }
    }
    
    // Reservoir sampling - Sample k items from stream of unknown size
    vector<int> reservoirSampling(vector<int>& stream, int k) {
        vector<int> reservoir(k);
        
        // Fill reservoir with first k elements
        for (int i = 0; i < k && i < stream.size(); i++) {
            reservoir[i] = stream[i];
        }
        
        // Process remaining elements
        for (int i = k; i < stream.size(); i++) {
            uniform_int_distribution<int> dist(0, i);
            int j = dist(rng);
            
            if (j < k) {
                reservoir[j] = stream[i];
            }
        }
        
        return reservoir;
    }
    
    // Monte Carlo estimation of π
    double estimatePi(int numSamples) {
        int pointsInCircle = 0;
        uniform_real_distribution<double> dist(-1.0, 1.0);
        
        for (int i = 0; i < numSamples; i++) {
            double x = dist(rng);
            double y = dist(rng);
            
            if (x * x + y * y <= 1.0) {
                pointsInCircle++;
            }
        }
        
        return 4.0 * pointsInCircle / numSamples;
    }
    
    // Random prime generation (Miller-Rabin primality test)
    bool millerRabinTest(long long n, int k = 5) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0) return false;
        
        // Write n-1 as d * 2^r
        long long d = n - 1;
        int r = 0;
        while (d % 2 == 0) {
            d /= 2;
            r++;
        }
        
        uniform_int_distribution<long long> dist(2, n - 2);
        
        for (int i = 0; i < k; i++) {
            long long a = dist(rng);
            long long x = fastPower(a, d, n);
            
            if (x == 1 || x == n - 1) continue;
            
            bool composite = true;
            for (int j = 0; j < r - 1; j++) {
                x = (x * x) % n;
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            
            if (composite) return false;
        }
        
        return true;
    }
    
private:
    long long fastPower(long long base, long long exp, long long mod) {
        long long result = 1;
        while (exp > 0) {
            if (exp & 1) result = (result * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
};

Geometric Algorithms

cpp

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    double dot(const Point& p) const { return x * p.x + y * p.y; }
    double cross(const Point& p) const { return x * p.y - y * p.x; }
    double norm() const { return sqrt(x * x + y * y); }
};

class GeometryAlgorithms {
public:
    // Distance between two points
    double distance(const Point& a, const Point& b) {
        return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    }
    
    // Check if three points are collinear
    bool areCollinear(const Point& a, const Point& b, const Point& c) {
        return abs((b - a).cross(c - a)) < 1e-9;
    }
    
    // Convex hull using Graham scan
    vector<Point> convexHull(vector<Point> points) {
        int n = points.size();
        if (n < 3) return points;
        
        // Find bottom-most point (or leftmost in case of tie)
        int minY = 0;
        for (int i = 1; i < n; i++) {
            if (points[i].y < points[minY].y || 
                (points[i].y == points[minY].y && points[i].x < points[minY].x)) {
                minY = i;
            }
        }
        swap(points[0], points[minY]);
        
        Point pivot = points[0];
        
        // Sort points by polar angle with respect to pivot
        sort(points.begin() + 1, points.end(), [&](const Point& a, const Point& b) {
            double cross = (a - pivot).cross(b - pivot);
            if (abs(cross) < 1e-9) {
                return distance(pivot, a) < distance(pivot, b);
            }
            return cross > 0;
        });
        
        // Graham scan
        vector<Point> hull;
        for (const Point& p : points) {
            while (hull.size() >= 2 && 
                   (hull[hull.size() - 1] - hull[hull.size() - 2]).cross(p - hull[hull.size() - 2]) <= 0) {
                hull.pop_back();
            }
            hull.push_back(p);
        }
        
        return hull;
    }
    
    // Area of polygon using shoelace formula
    double polygonArea(const vector<Point>& polygon) {
        double area = 0;
        int n = polygon.size();
        
        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            area += polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
        }
        
        return abs(area) / 2.0;
    }
};

🔬 Phân tích & Giải thích chi tiết

Algorithm Complexity Analysis

Algorithm	Time Complexity	Space Complexity	Use Case
GCD (Euclidean)	O(log min(a,b))	O(1)	Fraction simplification
Sieve of Eratosthenes	O(n log log n)	O(n)	Generate all primes up to n
Fast Exponentiation	O(log n)	O(1)	Modular arithmetic
Miller-Rabin	O(k log³ n)	O(1)	Probabilistic primality
nCr Precomputed	O(1)	O(n)	Combinatorics queries

Number Theory Applications

Cryptography:

RSA encryption: Uses large prime generation và modular arithmetic
Diffie-Hellman: Key exchange using discrete logarithms
Hash functions: Number theory properties for uniform distribution

Computer Science:

Hash tables: Prime numbers cho better distribution
Random number generation: Linear congruential generators
Error correction: Polynomial arithmetic over finite fields

💻 Ví dụ minh họa

Ví dụ 1: Mathematical Problem Solver

cpp

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

class MathematicalProblemSolver {
private:
    NumberTheory nt;
    ModularArithmetic ma;
    Combinatorics comb;
    RandomAlgorithms ra;
    
public:
    MathematicalProblemSolver() {
        comb.precompute(1000000);  // Precompute for efficiency
    }
    
    void solveProblemSet() {
        cout << "=== MATHEMATICAL ALGORITHMS DEMONSTRATION ===" << endl;
        
        // Problem 1: Find GCD and LCM
        cout << "\n📊 Problem 1: Number Theory" << endl;
        long long a = 48, b = 18;
        cout << "GCD(" << a << ", " << b << ") = " << nt.gcd(a, b) << endl;
        cout << "LCM(" << a << ", " << b << ") = " << nt.lcm(a, b) << endl;
        
        // Problem 2: Prime analysis
        cout << "\n🔍 Problem 2: Prime Analysis" << endl;
        int n = 100;
        auto primes = nt.sieveOfEratosthenes(n);
        vector<int> primeList;
        for (int i = 2; i <= n; i++) {
            if (primes[i]) primeList.push_back(i);
        }
        cout << "Primes up to " << n << ": ";
        for (int i = 0; i < min(10, (int)primeList.size()); i++) {
            cout << primeList[i] << " ";
        }
        cout << "... (total: " << primeList.size() << ")" << endl;
        
        // Problem 3: Prime factorization
        long long num = 60;
        auto factors = nt.primeFactorization(num);
        cout << "\nPrime factorization of " << num << ": ";
        for (int i = 0; i < factors.size(); i++) {
            cout << factors[i].first;
            if (factors[i].second > 1) cout << "^" << factors[i].second;
            if (i < factors.size() - 1) cout << " × ";
        }
        cout << endl;
        cout << "Number of divisors: " << nt.countDivisors(num) << endl;
        cout << "Sum of divisors: " << nt.sumOfDivisors(num) << endl;
        
        // Problem 4: Modular arithmetic
        cout << "\n🔢 Problem 3: Modular Arithmetic" << endl;
        long long base = 2, exp = 10, mod = 1000000007;
        cout << base << "^" << exp << " mod " << mod << " = " 
             << ma.fastPower(base, exp, mod) << endl;
        
        long long inv = ma.modInverse(7, mod);
        cout << "Modular inverse of 7 mod " << mod << " = " << inv << endl;
        cout << "Verification: (7 × " << inv << ") mod " << mod << " = " 
             << (7 * inv) % mod << endl;
        
        // Problem 5: Combinatorics
        cout << "\n🎲 Problem 4: Combinatorics" << endl;
        int n1 = 10, r1 = 3;
        cout << "C(" << n1 << "," << r1 << ") = " << comb.nCr(n1, r1) << endl;
        cout << "P(" << n1 << "," << r1 << ") = " << comb.nPr(n1, r1) << endl;
        
        int catN = 5;
        cout << "Catalan number C(" << catN << ") = " << comb.catalan(catN) << endl;
        
        int derangN = 4;
        cout << "Derangements of " << derangN << " items = " << comb.derangements(derangN) << endl;
        
        // Problem 6: Random algorithms
        cout << "\n🎰 Problem 5: Random Algorithms" << endl;
        
        // Estimate π using Monte Carlo
        double piEstimate = ra.estimatePi(1000000);
        cout << "π estimation (1M samples): " << fixed << setprecision(6) << piEstimate << endl;
        cout << "Actual π: " << M_PI << endl;
        cout << "Error: " << abs(piEstimate - M_PI) << endl;
        
        // Shuffle demonstration
        vector<int> deck = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        cout << "\nOriginal deck: ";
        for (int card : deck) cout << card << " ";
        
        ra.shuffle(deck);
        cout << "\nShuffled deck: ";
        for (int card : deck) cout << card << " ";
        cout << endl;
        
        // Reservoir sampling
        vector<int> stream = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        vector<int> sample = ra.reservoirSampling(stream, 5);
        cout << "\nReservoir sample (5 from 15): ";
        for (int item : sample) cout << item << " ";
        cout << endl;
        
        // Problem 7: Geometry
        cout << "\n📐 Problem 6: Computational Geometry" << endl;
        GeometryAlgorithms geo;
        
        vector<Point> points = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
        vector<Point> hull = geo.convexHull(points);
        
        cout << "Convex hull points: ";
        for (const Point& p : hull) {
            cout << "(" << p.x << "," << p.y << ") ";
        }
        cout << endl;
        
        double area = geo.polygonArea(hull);
        cout << "Convex hull area: " << fixed << setprecision(2) << area << endl;
    }
};

int main() {
    MathematicalProblemSolver solver;
    solver.solveProblemSet();
    
    return 0;
}

🏋️ Thực hành

Bài tập 1: Number Theory Library

Build comprehensive number theory library:

Prime checking với multiple methods
Prime generation với optimizations
Factorization algorithms
Euler's totient function

Bài tập 2: Cryptographic Primitives

Implement basic cryptographic operations:

RSA key generation
Modular exponentiation optimizations
Digital signature verification
Hash function based on number theory

Bài tập 3: Advanced Combinatorics

Solve complex combinatorial problems:

Inclusion-exclusion principle
Generating functions
Partitions và Bell numbers
Stirling numbers

Bài tập 4: Computational Geometry

Build geometry computation library:

Line intersection algorithms
Polygon triangulation
Closest pair of points
Voronoi diagrams

📋 Tóm tắt

Các điểm quan trọng

Number Theory:

GCD/LCM: Foundation cho fraction operations
Prime algorithms: Essential cho cryptography
Factorization: Key cho many mathematical problems
Modular arithmetic: Critical cho large number computations

Combinatorics:

nCr/nPr: Basic counting principles
Catalan numbers: Tree structures, valid parentheses
Derangements: Permutations với constraints
Stars and bars: Distribution problems

Applications:

Cryptography: RSA, digital signatures
Computer graphics: Transformations, collision detection
Probability: Monte Carlo methods, sampling
Optimization: Mathematical programming

Best Practices

Efficiency:

Precompute factorials cho combinatorics
Use fast exponentiation cho large powers
Implement sieve cho multiple prime queries
Optimize with appropriate data structures

Numerical Stability:

Handle large numbers với modular arithmetic
Use appropriate precision cho floating point
Check for overflow trong intermediate calculations
Implement error handling cho edge cases

Real-world Considerations:

Security: Use cryptographically secure random numbers
Performance: Profile mathematical operations
Accuracy: Understand floating point limitations
Scalability: Design for large input sizes

Course Completion

🎉 Congratulations! Bạn đã hoàn thành toàn bộ khóa học C++ từ cơ bản đến nâng cao!

Những gì đã học:

C++ Fundamentals: Syntax, data types, control structures
Advanced C++: Smart pointers, move semantics, lambda, multithreading
Algorithms: Complexity analysis, sorting, searching, DP, graphs
Problem Solving: Real-world applications và optimization techniques

Next Steps:

Practice: Solve problems on competitive programming platforms
Projects: Build real applications using learned concepts
Specialization: Deep dive into specific areas (graphics, AI, systems)
Community: Contribute to open source C++ projects

Mathematical algorithms complete the foundation cho advanced programming. Master these concepts để solve complex computational problems efficiently!

🔢 Thuật toán toán học (Mathematical Algorithms) ​

📖 Giới thiệu ​

🔧 Cú pháp ​

Number Theory Algorithms ​

Modular Arithmetic ​

Combinatorics ​

Random Algorithms ​

Geometric Algorithms ​

🔬 Phân tích & Giải thích chi tiết ​

Algorithm Complexity Analysis ​

Number Theory Applications ​

💻 Ví dụ minh họa ​

Ví dụ 1: Mathematical Problem Solver ​

🏋️ Thực hành ​

Bài tập 1: Number Theory Library ​

Bài tập 2: Cryptographic Primitives ​

Bài tập 3: Advanced Combinatorics ​

Bài tập 4: Computational Geometry ​

📋 Tóm tắt ​

Các điểm quan trọng ​

Best Practices ​

Course Completion ​