Toán học (Math)

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 5)

Toán học (Math)

Chinese Remainder Theorem

Thời gian (Time) O(log n)
Không gian (Space) O(1)

Mô tả nguyên lý

Giải hệ phương trình đồng dư tuyến tính trong lý thuyết số.

Cài đặt mẫu (Implementation)

// Thuật toán tìm nghiệm đồng dư dựa trên nghịch đảo modulo.
Toán học (Math)

Euclidean GCD

Thời gian (Time) O(log(min(a, b)))
Không gian (Space) O(1)

Mô tả nguyên lý

Thuật toán tìm ước chung lớn nhất (GCD) của hai số nguyên.

Cài đặt mẫu (Implementation)

function gcd($a, $b) {
    while ($b != 0) {
        $t = $b;
        $b = $a % $b;
        $a = $t;
    }
    return $a;
}
Toán học (Math)

Modular Exponentiation

Thời gian (Time) O(log b)
Không gian (Space) O(1)

Mô tả nguyên lý

Tính lũy thừa số mũ lớn theo modulo (a^b mod m) một cách hiệu quả.

Cài đặt mẫu (Implementation)

function powerMod($base, $exp, $mod) {
    $res = 1;
    $base = $base % $mod;
    while ($exp > 0) {
        if ($exp % 2 == 1) $res = ($res * $base) % $mod;
        $base = ($base * $base) % $mod;
        $exp = floor($exp / 2);
    }
    return $res;
}
Toán học (Math)

Prime Factorization

Thời gian (Time) O(√n)
Không gian (Space) O(1)

Mô tả nguyên lý

Phân tích một số nguyên thành tích các thừa số nguyên tố.

Cài đặt mẫu (Implementation)

function primeFactors($n) {
    $factors = [];
    for ($i = 2; $i * $i <= $n; $i++) {
        while ($n % $i == 0) {
            $factors[] = $i;
            $n = $n / $i;
        }
    }
    if ($n > 2) $factors[] = $n;
    return $factors;
}
Toán học (Math)

Sieve of Eratosthenes

Thời gian (Time) O(n log log n)
Không gian (Space) O(n)

Mô tả nguyên lý

Thuật toán tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số n cho trước.

Cài đặt mẫu (Implementation)

function sieve($n) {
    $prime = array_fill(0, $n + 1, true);
    for ($p = 2; $p * $p <= $n; $p++) {
        if ($prime[$p] == true) {
            for ($i = $p * $p; $i <= $n; $i += $p) $prime[$i] = false;
        }
    }
    $primes = [];
    for ($p = 2; $p <= $n; $p++) if ($prime[$p]) $primes[] = $p;
    return $primes;
}