Toán học

Wiki › Thuật toán

huunguyen · Last updated 28, Tháng 3, 2026, 22:50

Số nguyên tố

Kiểm tra số nguyên tố — $O (\sqrt{N})$

bool is_prime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i*i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

Sàng Eratosthenes — $O (N \log \log N)$

Tìm tất cả số nguyên tố đến $N$ .

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;
}

def sieve(n):
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return is_prime

GCD và LCM

// C++17: __gcd hoặc std::gcd
#include <numeric>
int g = gcd(a, b);
int l = lcm(a, b);  // = a / gcd(a,b) * b

// Tự cài (Euclidean algorithm)
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

from math import gcd
g = gcd(a, b)
l = a * b // gcd(a, b)

Đồng dư và Modular Arithmetic

Khi bài yêu cầu đáp án modulo $10^{9} + 7$ :

const long long MOD = 1e9+7;

// Cộng, trừ, nhân
(a + b) % MOD
(a - b + MOD) % MOD
(a * b) % MOD

// Lũy thừa nhanh
long long power(long long a, long long n, long long mod) {
    long long res = 1; a %= mod;
    while (n > 0) {
        if (n & 1) res = res*a % mod;
        a = a*a % mod; n >>= 1;
    }
    return res;
}

// Nghịch đảo modulo (mod phải là số nguyên tố)
long long inv(long long a) { return power(a, MOD-2, MOD); }

// Chia trong modulo
(a * inv(b)) % MOD

Tổ hợp (Combinatorics)

Tính $C (n, k) \mod p$

const int MAXN = 1e6+5;
long long fact[MAXN], inv_fact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = power(fact[MAXN-1], MOD-2, MOD);
    for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

from math import comb
print(comb(10, 3))  # C(10,3) = 120

MOD = 10**9+7
# Tính C(n,k) mod p với n,k lớn: dùng precompute như C++

Phân tích thừa số nguyên tố

map<int,int> factorize(int n) {
    map<int,int> factors;
    for (int i = 2; i*i <= n; i++)
        while (n % i == 0) { factors[i]++; n /= i; }
    if (n > 1) factors[n]++;
    return factors;
}

Bảng công thức thường dùng

Công thức	Ý nghĩa
$a^{b} \mod p$	Lũy thừa nhanh: $O (\log b)$
$gcd (a, b)$	Euclid: $O (\log min (a, b))$
$C (n, k) \mod p$	Precompute factorial: $O (N)$
Số ước của $N$	$O (\sqrt{N})$
Số nguyên tố đến $N$	Sàng: $O (N \log \log N)$

Bình luận

Không có bình luận tại thời điểm này.

Toán học

Số nguyên tố

Kiểm tra số nguyên tố — O(N)

Sàng Eratosthenes — O(NloglogN)

GCD và LCM

Đồng dư và Modular Arithmetic

Tổ hợp (Combinatorics)

Tính C(n,k)modp

Phân tích thừa số nguyên tố

Bảng công thức thường dùng

Bình luận

Kiểm tra số nguyên tố — $O (\sqrt{N})$

Sàng Eratosthenes — $O (N \log \log N)$

Tính $C (n, k) \mod p$