Hướng dẫn giải của Phân tích thừa số nguyên tố

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hang2k, lephuochauhungvuong, khang1901

Hiểu bài toán

Cho một số nguyên dương n (2 ≤ n ≤ 10^18). Nhiệm vụ là phân tích n thành tích các thừa số nguyên tố và in ra từng cặp (thừa số nguyên tố p, số mũ k) tương ứng với p^k trong phân tích đó. Các thừa số nguyên tố cần được sắp xếp tăng dần.

Các cách tiếp cận

Cách Phân tích bằng Pollard's Rho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll mul(ll a, ll b, ll mod) {
    return (__int128)a * b % mod;
}

ll power(ll a, ll d, ll mod) {
    ll res = 1;
    while (d) {
        if (d & 1) res = mul(res, a, mod);
        a = mul(a, a, mod);
        d >>= 1;
    }
    return res;
}

bool miller_rabin(ll n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1, s = 0;
    while (d % 2 == 0) d /= 2, s++;
    for (ll a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        if (a % n == 0) continue;
        ll x = power(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool comp = true;
        for (int r = 1; r < s; r++) {
            x = mul(x, x, n);
            if (x == n - 1) {
                comp = false;
                break;
            }
        }
        if (comp) return false;
    }
    return true;
}

ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

ll pollard_rho(ll n) {
    if (n == 1) return 1;
    if (n % 2 == 0) return 2;
    ll x = 2 + rand() % (n - 2);
    ll y = x;
    ll c = 1 + rand() % (n - 1);
    ll d = 1;
    while (d == 1) {
        x = (mul(x, x, n) + c) % n;
        y = (mul(y, y, n) + c) % n;
        y = (mul(y, y, n) + c) % n;
        d = gcd(abs(x - y), n);
        if (d == n) return pollard_rho(n);
    }
    return d;
}

map<ll, int> factors;

void factorize(ll n) {
    if (n == 1) return;
    if (miller_rabin(n)) {
        factors[n]++;
        return;
    }
    ll divisor = pollard_rho(n);
    factorize(divisor);
    factorize(n / divisor);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    if (cin >> n) {
        factorize(n);
        for (auto p : factors) {
            cout << p.first << " " << p.second << "\n";
        }
    }
    return 0;
}

Time Complexity: O(n^{1/4})
Space Complexity: O(log n)

Đây là phương pháp chuẩn để phân tích số lớn (trên 10^12).

Miller-Rabin Primality Test: Kiểm tra tính nguyên tố của n. Nếu n là số nguyên tố, ta đã tìm thấy một thừa số.
Pollard's Rho Algorithm: Nếu n là hợp số, tìm một thừa số không tầm thường d của n bằng cách sử dụng chu kỳ Floyd. Thuật toán này có độ phức tạp khoảng O(n^{1/4}).
Thuật toán đệ quy: Chia n thành d và n/d, rồi áp dụng lại thuật toán cho từng phần.
Lưu trữ: Sử dụng map<ll, int> để lưu trữ các thừa số và số mũ của chúng, tự động sắp xếp tăng dần. Độ phức tạp thời gian trung bình là O(n^{1/4}), đủ nhanh cho n ≤ 10^18.

Cách Quy hoạch động với Sieve

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    // Code này chỉ hoạt động cho n <= 10^6 do giới hạn bộ nhớ và thời gian sieve
    // Đây là minh họa cho cách tiếp cận đơn giản
    ll n;
    cin >> n;

    // Tối ưu: chỉ cần sieve đến sqrt(n)
    ll limit = (ll)sqrt(n);
    vector<ll> primes;
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (ll i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (ll j = i * i; j <= limit; j += i)
                is_prime[j] = false;
        }
    }

    for (ll p : primes) {
        if (p * p > n) break;
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            cout << p << " " << cnt << "\n";
        }
    }
    if (n > 1) {
        cout << n << " " << 1 << "\n";
    }
    return 0;
}

Time Complexity: O(sqrt(n))
Space Complexity: O(sqrt(n))

Đây là phương pháp phân tích thừa số nguyên tố bằng cách thử các số nguyên tố.

Sieve of Eratosthenes: Tạo danh sách các số nguyên tố từ 2 đến căn bậc hai của n.
Thử các thừa số: Duyệt qua các số nguyên tố đã tạo và thử chia n cho chúng.
Xử lý số còn lại: Nếu sau khi chia hết cho các số nguyên tố nhỏ hơn sqrt(n) mà n vẫn lớn hơn 1, thì n đó là số nguyên tố. Phương pháp này chỉ hiệu quả khi n nhỏ (khoảng < 10^12) hoặc khi ta chỉ cần tìm các thừa số nhỏ.

Cách Thử các ước số lẻ

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n;
    cin >> n;

    vector<pair<ll, ll>> factors;

    // Xử lý thừa số 2
    if (n % 2 == 0) {
        ll cnt = 0;
        while (n % 2 == 0) {
            n /= 2;
            cnt++;
        }
        factors.push_back({2, cnt});
    }

    // Thử các số lẻ từ 3 đến sqrt(n)
    for (ll i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            factors.push_back({i, cnt});
        }
    }

    // Nếu còn lại số lớn hơn 1 thì đó là số nguyên tố
    if (n > 1) {
        factors.push_back({n, 1});
    }

    // In kết quả (đã được sắp xếp do duyệt từ nhỏ đến lớn)
    for (auto p : factors) {
        cout << p.first << " " << p.second << "\n";
    }

    return 0;
}

Time Complexity: O(sqrt(n))
Space Complexity: O(1)

Đây là phương pháp brute force đơn giản nhất.

Xử lý thừa số 2: Xử lý riêng biệt để tăng tốc độ.
Duyệt bước nhảy 2: Duyệt các số lẻ từ 3 đến sqrt(n) để tìm ước số.
Tối ưu hóa: Nếu tìm thấy ước số i, chia hết cho i và cập nhật n. Độ phức tạp O(sqrt(n)). Với n = 10^18, sqrt(n) = 10^9, quá chậm.

Phân tích độ phức tạp

Cách tiếp cận	Time	Space	Tên
1	O(n^{1/4})	O(log n)	Phân tích bằng Pollard's Rho
2	O(sqrt(n))	O(sqrt(n))	Quy hoạch động với Sieve
3	O(sqrt(n))	O(1)	Thử các ước số lẻ

Bài học kinh nghiệm

Với n lớn (10^18), thuật toán Pollard's Rho là bắt buộc để phân tích trong thời gian thực.
Việc kiểm tra tính nguyên tố (Miller-Rabin) cần được thực hiện trước khi tìm thừa số để tránh các thao tác không cần thiết.
Sử dụng __int128 hoặc các hàm nhân mod an toàn là bắt buộc khi làm việc với số 64-bit.

Lỗi thường gặp

Tràn số khi tính toán bình phương hoặc nhân các số lớn. Cần sử dụng __int128 hoặc mulmod.
Lựa chọn sai bộ cơ sở cho Miller-Rabin có thể dẫn đến kết quả kiểm tra nguyên tố sai (số giả nguyên tố).
Pollard's Rho có thể đi vào vòng lặp vô hạn nếu không có cơ chế tái khởi tạo (ví dụ trả về đệ quy).

Bình luận

Please read the guidelines before commenting.

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