Giới thiệu bài toán xử lý thừa số nguyên tố

Khi giải quyết các bài toán liên quan đến số học lớn trong kỳ thi lập trình như CCF, việc phân tích nhân tử là bước cơ bản nhưng yêu cầu độ chính xác và hiệu suất cao. Đề bài đặt ra yêu cầu xác định các thừa số nguyên tố của một số n với điều kiện loại bỏ những thừa số có số mũ nhỏ hơn ngưỡng k. Phạm vi dữ liệu đầu vào thường nằm trong khoảng 1 < n <= 10^10, đòi hỏi thuật toán phải hoạt động tốt trong giới hạn thời gian.

Phương pháp 1: Sử dụng sàng Eratosthenes tối ưu

Một cách tiếp cận trực quan là tiền tính toán danh sách số nguyên tố để phục vụ cho nhiều lần truy vấn. Tuy nhiên, đối với giá trị n lên tới 10^10, việc sàng đến 10^8 là không cần thiết vì các thừa số nguyên tố chỉ xuất hiện đến căn bậc hai của n. Dưới đây là phiên bản cải tiến sử dụng bộ nhớ hợp lý hơn và cấu trúc mã rõ ràng.

#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAX_PRIME_SQRT = 100005; // Căn bậc hai của 10^10
bool isPrime[MAX_PRIME_SQRT];
vector<int> primeList;

void initSieve() {
    fill(isPrime, isPrime + MAX_PRIME_SQRT, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int p = 2; p * p < MAX_PRIME_SQRT; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i < MAX_PRIME_SQRT; i += p)
                isPrime[i] = false;
        }
    }
    
    for (int p = 2; p < MAX_PRIME_SQRT; p++) {
        if (isPrime[p]) {
            primeList.push_back(p);
        }
    }
}

ll solveDecomposition(ll number, int thresholdK) {
    ll result = number;
    
    for (size_t i = 0; i < primeList.size(); ++i) {
        ll p = primeList[i];
        if (p * p > number) break;
        
        if (number % p == 0) {
            int exponent = 0;
            while (number % p == 0) {
                number /= p;
                exponent++;
            }
            
            if (exponent < thresholdK) {
                for (int j = 0; j < exponent; j++) {
                    result /= p;
                }
            }
        }
    }
    
    if (number > 1 && thresholdK == 1) {
        // Trường hợp còn lại là số nguyên tố lớn hơn căn bậc hai ban đầu
        // Nếu k=1 thì giữ lại, nếu k>1 thì loại bỏ (do exponent=1 < k)
        if (thresholdK > 1) result /= number; 
    } else if (number > 1 && thresholdK > 1) {
         // Nếu k > 1 và còn số nguyên tố sót lại (exponent = 1) thì cần loại
          result /= number;
    }
    
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    initSieve();
    int queries;
    cin >> queries;
    
    while (queries--) {
        ll n;
        int k;
        cin >> n >> k;
        cout << solveDecomposition(n, k) << endl;
    }
    return 0;
}

Phương pháp 2: Kiểm tra đồng thời (Trial Division)

Trong trường hợp số lượng truy vấn ít mà phạm vi số lớn, việc duyệt từ 2 đến sqrt(n) ngay trong hàm xử lý sẽ tiết kiệm bộ nhớ đáng kể so với việc xây dựng bảng sàng toàn cục. Cách này giảm tải chi phí khởi tạo và tránh giới hạn bộ nhớ khi n thay đổi động.

#include <cstdio>

typedef long long ll;

// Hàm thực hiện logic loại bỏ thừa số
void processNumber(ll originalVal, int minPower) {
    ll tempNum = originalVal;
    ll numerator = 1; // Phần được giữ lại
    
    // Duyệt qua các ước số tiềm năng
    for (ll i = 2; i * i <= tempNum; ++i) {
        if (tempNum % i != 0) continue;
        
        int count = 0;
        while (tempNum % i == 0) {
            tempNum /= i;
            count++;
        }
        
        // Nếu số mũ đủ lớn thì giữ lại phần tử này
        if (count >= minPower) {
            for (int j = 0; j < count; ++j) {
                numerator *= i;
            }
        }
    }
    
    // Xử lý phần còn lại nếu là số nguyên tố lớn
    if (tempNum > 1) {
        if (1 >= minPower) { // Exponent luôn bằng 1 ở đây
             numerator *= tempNum;
        }
    }
    
    // In kết quả: nếu không giữ được gì cả trả về 1, ngược lại là numerator
    // Lưu ý: Logic gốc có thể tùy biến theo yêu cầu cụ thể của đề bài về việc trả về giá trị bị chia hay giá trị còn lại
    if (numerator == 1) {
        printf("1\n");
    } else {
        printf("%lld\n", numerator);
    }
}

int main() {
    int qCount;
    if (scanf("%d", &qCount) != 1) return 0;
    
    while (qCount--) {
        ll val;
        int limit;
        scanf("%lld%d", &val, &limit);
        processNumber(val, limit);
    }
    return 0;
}