Toán học
Extended Euclidean Algorithm
ID: #70
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ý
Tìm ước chung lớn nhất đồng thời tính các hệ số x, y sao cho ax + by = gcd.
Cài đặt mẫu (Implementation)
function extendedGCD($a, $b, &$x, &$y) {
if ($a == 0) { $x = 0; $y = 1; return $b; }
$x1 = 1; $y1 = 1;
$gcd = extendedGCD($b % $a, $a, $x1, $y1);
$x = $y1 - floor($b / $a) * $x1;
$y = $x1;
return $gcd;
}
Toán học
Matrix Exponentiation
ID: #69
Xem trên trang chủ
Thời gian (Time)
O(k^3 log n)
Không gian (Space)
O(k^2)
Mô tả nguyên lý
Tính lũy thừa ma trận lớn trong thời gian logarithmic.
Cài đặt mẫu (Implementation)
// Nhân ma trận nhị phân kết hợp lũy thừa chia đôi số mũ.
Toán học
Miller-Rabin Primality Test
ID: #71
Xem trên trang chủ
Thời gian (Time)
O(k log^3 n)
Không gian (Space)
O(1)
Mô tả nguyên lý
Thuật toán kiểm tra tính nguyên tố probabilistic cho số rất lớn.
Cài đặt mẫu (Implementation)
// Sử dụng kiểm tra tính đồng dư xác suất qua nhiều cơ sở khác nhau.
Toán học
Pollard Rho Algorithm
ID: #72
Xem trên trang chủ
Thời gian (Time)
O(n^(1/4))
Không gian (Space)
O(1)
Mô tả nguyên lý
Thuật toán phân tích thừa số nguyên tố ngẫu nhiên cực nhanh.
Cài đặt mẫu (Implementation)
// Sử dụng chu kỳ sinh số giả ngẫu nhiên kết hợp thuật toán Floyd.