Toán học (Math)
Chinese Remainder Theorem
ID: #35
Xem trên trang chủ
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
ID: #31
Xem trên trang chủ
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
ID: #33
Xem trên trang chủ
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
ID: #34
Xem trên trang chủ
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
ID: #32
Xem trên trang chủ
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;
}