tiny-functions ứng dụng trong lập trình thi đấu

SỐ HỌC

Số nguyên tố

Kiểm tra số nguyên X có phải là số nguyên tố hay không?

Input: Số nguyên X

Output: True: nếu X là số nguyên tố / False trong trường hợp ngược lại

Phương pháp phát hiện ước

// Check X is Prime or not
bool isPrime(int X) {
    if (X < 2) return false;
    for (int i = 2; i <= sqrt(X); ++i) {
        if (X % i == 0) return false;
    }
    return true;
}

Phương pháp phát hiện ước bước nhảy 2

Bằng nhận xét toán học ta có thể dễ dàng nhận thấy 2 là số nguyên tố chẵn duy nhất, các số nguyên tố còn lại đều là số lẻ nên ta sẽ có phiên bản cải tiến như sau:

bool isPrime(int X) {
    if (X < 2) return false;
    if (X == 2) return true;
    if (X % 2 == 0) return false;
    for (int i = 3; i * i <= X; i += 2) {
        if (X % i == 0) return false;
    }
    return true;
}

Phương pháp phát hiện ước bước nhảy 6

Nhận thấy rằng các số nguyên tố lớn hơn 3 đều có dạng \( 6k \pm 1 \) nên ta có thể kiểm tra ước thông qua bước nhảy 6:

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

So sánh tốc độ của các phương pháp kiểm tra tính nguyên tố :

Có thể dễ dàng nhận thấy phương pháp kiểm tra tính nguyên tố theo 3 phương pháp có khác biệt về tốc độ thực thi trên thực tế. Để có thể có cái nhìn khách quan, ta có thể so sánh tốc độ của 3 phương pháp bằng đoạn mã bên dưới. Kết quả sẽ giúp cho bạn lựa chọn được phương pháp phù hợp để áp dụng trong các trường hợp cụ thể.

Phương pháp	Số phép chia cần kiểm tra
Phương pháp phát hiện ước trong giới hạn \( \sqrt {n} \)	\( \sqrt {n} \)
Phương pháp bước nhảy 2 trong giới hạn \( \sqrt {n} \)	\( \sqrt {n} \)
Phương pháp bước nhảy 6 giới hạn \( \sqrt {n} \)	\( \frac {\sqrt {n}} {3} \)

#include <iostream>
#include <cmath>
#include <chrono>

using namespace std;
using namespace std::chrono;

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

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

bool isPrime3(unsigned long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    for (unsigned long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

void testSpeed(unsigned long long n) {
    auto start1 = high_resolution_clock::now();
    isPrime1(n);
    auto stop1 = high_resolution_clock::now();
    
    auto start2 = high_resolution_clock::now();
    isPrime2(n);
    auto stop2 = high_resolution_clock::now();
    
    auto start3 = high_resolution_clock::now();
    isPrime3(n);
    auto stop3 = high_resolution_clock::now();

    cout << "Runtime O(n): " 
         << duration_cast<microseconds>(stop1 - start1).count() << " μs\n";
    cout << "Runtime O(sqrt(n)): " 
         << duration_cast<microseconds>(stop2 - start2).count() << " μs\n";
    cout << "Runtime O(sqrt(n)/3): " 
         << duration_cast<microseconds>(stop3 - start3).count() << " μs\n";
}

int main() {
    unsigned long long n = 1e9+7; // Một số nguyên tố lớn
    testSpeed(n);
    return 0;
}

Sàng nguyên tố

Tạo sàng nguyên tố phục vụ cho các yêu cầu kiểm tra tính nguyên tố nhiều lần với nhiều giá trị khác nhau trong cùng một lần xử lý

Input: vector<bool> seive để lưu sàng nguyên tố, số nguyên maxN là giới hạn của sàng

Output: vector<bool> seive đã được xử lý

void mkSeive(vector<bool>& seive, int maxN) {
    seive.assign(maxN + 1, true);
    seive[0] = seive[1] = false; // 0 và 1 không phải số nguyên tố

    for (int p = 2; p * p <= maxN; ++p) {
        if (seive[p]) { // Nếu p là số nguyên tố
            for (int multiple = p * p; multiple <= maxN; multiple += p) {
                seive[multiple] = false; // Đánh dấu bội số của p
            }
        }
    }
}

Độ phức tạp:

• \( O(n \log n) \) – Tốc độ rất nhanh.
• Bộ nhớ O(n) – Dùng vector seive.

Đếm ước

Đếm số lượng ước số của số nguyên X

Input: Số nguyên X

Output: Số lượng ước của số nguyên X

int countDivisors(int X) {
    int count = 0;
    for (int i = 1; i * i <= X; ++i) {
        if (X % i == 0) {
            if (i * i == X) { // Nếu i là căn bậc hai của X
                count += 1;
            } else { // Nếu i và X/i là hai số khác nhau
                count += 2;
            }
        }
    }
    return count;
}

Độ phức tạp:

• O(\( \sqrt{X} \) ), nhanh hơn so với cách kiểm tra tất cả các số từ 1 đến X (O(X)).

Ước chung lớn nhất/ Bội chung nhỏ nhất

Input: 2 số nguyên dương a và b

Output: Ước chung lớn nhất / Bội chung nhỏ nhất (tùy yêu cầu)

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    return (a * b)/gcd(a, b);
}

Lưu ý: Có thể sử dụng phương pháp thiết kế hàm GCD bằng đệ quy để dễ nhớ. Tuy nhiên trong một số bài toán có giá trị a, b đủ lớn sẽ dẫn tới việc tràn bộ nhớ nên ở đây chỉ giới thiệu phương pháp tính GCD dựa vào thuật toán Euclid

Hàm tính số mũ nhanh (Exponentiation by Squaring)

Input: số nguyên a và b

Output: Giá trị của \( a^b \)

long long fastExpo(long long a, long long b) {
    long long result = 1;
    while (b > 0) {
        if (b & 1) { // Nếu b lẻ
            result *= a;
        }
        a *= a;  // Bình phương cơ số
        b >>= 1; // Chia b cho 2
    }
    return result;
}

Hàm Tính Số Mũ Modulo

Khi tính \( a^b \mod m \), ta dùng quy tắc:

\( (a*b) \mod m = ((a \mod m) * (b \mod m)) \mod m\)

Input: a , b , m

Output: \( a^b \mod m \)

long long fastExpoMod(long long a, long long b, long long mod) {
    long long result = 1;
    a %= mod; // Giảm cơ số theo mod

    while (b > 0) {
        if (b & 1) {
            result = (result * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return result;
}

Hàm đảo ngược số nguyên

Input: Số nguyên N

Output: Số nguyên rev là giá trị số đảo ngược của N

long long reverseNumber(long long n) {
    long long rev = 0;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n /= 10;
    }
    return rev;
}

Kiểm tra lũy thừa 2

Input: Số nguyên N

Output: True: nếu n có giá trị dạng \( 2^x \)

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Đếm số chữ số

Input: số nguyên N

Output: Số lượng chữ số của N

int countDigits(long long n) {
    return n == 0 ? 1 : (int)log10(n) + 1;
}

Chuyển đổi hệ cơ số Thập phân <-> Nhị phân

vector<int> Dec2Bin(long long n) {
    vector<int>A;
    while(n>0) {
        A.push_back(n%2);
        n/=2;
    }
    reverse(A.begin(), A.end());
    return A;
}
long long Bin2Dec(vector<int> bin){
    long long res_n=0, pow2=1;
	for(int i=bin.size()-1; 0<=i; i--) {
		res_n+=bin[i]*pow2;
		pow2*=2;
	}
	return res_n;
}

Sinh số ngẫu nhiên trong khoảng [L,R]

Input: Cặp giá trị \( L \le R \)
Output: Giá trị ngẫu nhiên \( X \in [L, R] \)

#include <random>

int randomInt(int L, int R) {
    static std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<int> dist(L, R);
    return dist(rng);
}

Ứng dụng: Sinh số ngẫu nhiên trong lập trình thi đấu hoặc kiểm thử.

Xử lý Xâu

Kiểm tra xâu đối xứng (Palindrome)

Input: xâu ký tự S

Output: True nếu S có dạng đối xứng / False trong trường hợp ngược lại.

bool isPalindrome(const std::string& s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        ++l; --r;
    }
    return true;
}

Tách số ra khỏi xâu và lưu vào vector:

Input: Xâu S

Output: vector<int> numbers chứa các số xuất hiện trong xâu, với mỗi số xác định là đoạn ký tự liên tiếp chỉ toàn chữ số

vector<int> extractNumbers(const string &s) {
    vector<int> numbers;
    int num = 0;
    bool hasNum = false;

    for (size_t i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9') { // Kiểm tra nếu ký tự là số
            num = num * 10 + (s[i] - '0');
            hasNum = true;
        } else if (hasNum) { // Nếu gặp ký tự không phải số sau khi đã đọc số
            numbers.push_back(num);
            num = 0;
            hasNum = false;
        }
    }
    
    if (hasNum) numbers.push_back(num); // Thêm số cuối cùng nếu có

    return numbers;
}

Tạo mã Hash của xâu (Rabin-Karp)

Input: Xâu S

Output: Xâu S được mã hóa thành một giá trị hash (tìm hiểu thêm về hash)

const int P = 31;
const int MOD = 1e9 + 7;

vector<long long> computeHash(const string &s) {
    int n = s.size();
    vector<long long> hash(n + 1, 0), power(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        power[i] = (power[i - 1] * P) % MOD;
        hash[i] = (hash[i - 1] * P + (s[i - 1] - 'a' + 1)) % MOD;
    }
    return hash;
}

Z-function (Tìm xâu con xuất hiện nhiều lần)

Z-function thường dùng trong:

• Kiểm tra xem chuỗi có cấu trúc lặp không (ví dụ, chuỗi ababab có thể viết lại thành ab lặp 3 lần).
• Tính toán số lần một mẫu xuất hiện như tiền tố trong nhiều vị trí.
• Các bài toán về border (tiền tố cũng là hậu tố).

Input: Xâu S

Output: Mảng Z-function của xâu

vector<int> ZFunction(const string &s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) {
            l = i; r = i + z[i] - 1;
        }
    }
    return z;
}

Tiền xử lý KMP (Prefix Function)

Dùng cho bước tiền xử lý trước khi áp dụng thuật toán KMP để so khớp xâu

vector<int> prefixFunction(const string &s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}