Toán học

Wiki › Thuật toán

huunguyen · Last updated 8, Tháng 4, 2026, 15:30

Số nguyên tố

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

// Sàng Eratosthenes: O(N log log N)
vector<bool> sieve(int n) {
    vector<bool> p(n+1,true); p[0]=p[1]=false;
    for (int i=2; i*i<=n; i++) if (p[i]) for (int j=i*i; j<=n; j+=i) p[j]=false;
    return p;
}

GCD và LCM

#include <numeric>
int g = gcd(a, b);
int l = lcm(a, b);

Thuật toán Euclid mở rộng

Tìm $x, y$ sao cho $a x + b y = gcd (a, b)$ :

long long ext_gcd(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 g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Phương trình ax ≡ c (mod m) có nghiệm khi gcd(a,m) | c
// Nghiệm: x = x0 * (c/g) % (m/g), với x0 từ ext_gcd(a, m, x0, y0)
long long solve_linear(long long a, long long c, long long m) {
    long long x, y;
    long long g = ext_gcd(a, m, x, y);
    if (c % g != 0) return -1;   // vô nghiệm
    long long mod = m / g;
    return (x % mod * (c / g) % mod + mod) % mod;
}

Modular Arithmetic

const long long MOD = 1e9+7;
(a+b)%MOD
(a-b+MOD)%MOD
a*b%MOD

// Lũy thừa nhanh O(log n)
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 nguyên tố)
long long inv(long long a) { return power(a, MOD-2, MOD); }

Định lý số dư Trung Hoa (CRT)

Hệ phương trình $x \equiv r_{i} (\mod m_{i})$ với các $m_{i}$ đôi một nguyên tố cùng nhau có nghiệm duy nhất modulo $M = \prod m_{i}$ :

// Hợp hai phương trình: x ≡ r1 (mod m1) và x ≡ r2 (mod m2)
// Yêu cầu: gcd(m1, m2) = 1
pair<long long, long long> crt(long long r1, long long m1, long long r2, long long m2) {
    long long x, y;
    long long g = ext_gcd(m1, m2, x, y);
    // g phải là 1
    long long lcm = m1 / g * m2;
    long long ans = (r1 + m1 * ((r2 - r1) % m2 * x % m2 + m2)) % lcm;
    return {ans, lcm};
}

// Hợp nhiều phương trình:
long long r = 0, m = 1;
for (auto [ri, mi] : equations) {
    auto [new_r, new_m] = crt(r, m, ri, mi);
    r = new_r; m = new_m;
}

CRT tổng quát (không yêu cầu nguyên tố cùng nhau):

// x ≡ r1 (mod m1), x ≡ r2 (mod m2)
// Có nghiệm khi gcd(m1,m2) | (r2-r1)
pair<long long,long long> crt_general(long long r1, long long m1, long long r2, long long m2) {
    long long x, y, g = ext_gcd(m1, m2, x, y);
    if ((r2 - r1) % g != 0) return {-1, -1};  // vô nghiệm
    long long lcm = m1 / g * m2;
    long long ans = (r1 + m1 * ((r2 - r1) / g % (m2/g) * x % (m2/g) + m2/g)) % lcm;
    return {(ans % lcm + lcm) % lcm, lcm};
}

Tổ hợp $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;
}

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

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

Bảng công thức

	Độ phức tạp
Kiểm tra nguyên tố	$O (\sqrt{N})$
Sàng nguyên tố đến $N$	$O (N \log \log N)$
GCD	$O (\log min (a, b))$
Extended GCD	$O (\log min (a, b))$
Lũy thừa nhanh $a^{b}$	$O (\log b)$
$C (n, k) \mod p$ (precompute)	$O (N)$ build, $O (1)$ query
CRT (2 phương trình)	$O (\log min (m_{1}, m_{2}))$

Xem thêm: FFT cho nhân đa thức $O (N \log N)$ .

Child pages

Bình luận

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