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, vohuongtk32c, khang1901, chumanhlaocai

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 thừa số nguyên tố và in ra các cặp (thừa số nguyên tố, số mũ) theo thứ tự tăng dần của thừa số nguyên tố.

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

Cách Trial Division với tối ưu hóa
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll n;
    cin >> n;
    // Chia hết cho 2
    if (n % 2 == 0) {
        int cnt = 0;
        while (n % 2 == 0) {
            n /= 2;
            cnt++;
        }
        cout << 2 << " " << cnt << "\n";
    }
    // Chia hết cho các số lẻ từ 3 đến sqrt(n)
    for (ll i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << " " << cnt << "\n";
        }
    }
    // Nếu n vẫn lớn hơn 1, thì n đó là số nguyên tố
    if (n > 1) {
        cout << n << " " << 1 << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}
  • Time Complexity: O(sqrt(n))
  • Space Complexity: O(1)

Phương pháp này dựa trên việc kiểm tra chia hết. Đầu tiên, ta xử lý thừa số 2 riêng. Sau đó, ta duyệt qua tất cả các số lẻ từ 3 đến căn bậc hai của n. Nếu tìm được một số i chia hết n, ta đếm số mũ của i và chia n cho i cho đến khi không còn chia hết. Cuối cùng, nếu n còn lại lớn hơn 1, phần còn lại đó chính là một số nguyên tố. Do n có thể lên tới 10^18, phương pháp này chỉ hiệu quả khi n có các thừa số nguyên tố nhỏ. Nếu n là số nguyên tố lớn hoặc tích của hai số nguyên tố lớn, phương pháp này sẽ quá thời gian.

Cách Pollard's Rho và Miller-Rabin
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u128 = __uint128_t;

// Nhân an toàn bằng 128-bit
ll mulmod(ll a, ll b, ll mod) {
    return (u128)a * b % mod;
}

// Lũy thừa nhanh
ll powmod(ll a, ll d, ll mod) {
    ll res = 1;
    while(d) {
        if(d & 1) res = mulmod(res, a, mod);
        a = mulmod(a, a, mod);
        d >>= 1;
    }
    return res;
}

// Miller-Rabin: Kiểm tra tính nguyên tố
bool isPrime(ll n) {
    if(n < 2) return false;
    for(ll p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if(n % p == 0) return n == p;
    }
    ll d = n - 1, s = 0;
    while((d & 1) == 0) {
        d >>= 1;
        s++;
    }
    for(ll a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        if(a % n == 0) continue;
        ll x = powmod(a, d, n);
        if(x == 1 || x == n - 1) continue;
        bool comp = true;
        for(int r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if(x == n - 1) {
                comp = false;
                break;
            }
        }
        if(comp) return false;
    }
    return true;
}

// Pollard's Rho: Phân tích n thành các thừa số
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll pollard_rho(ll n) {
    if (n == 1) return 1;
    if (n % 2 == 0) return 2;
    ll x = uniform_int_distribution<ll>(2, n - 1)(rng);
    ll c = uniform_int_distribution<ll>(1, n - 1)(rng);
    ll y = x;
    ll g = 1;
    while (g == 1) {
        x = (mulmod(x, x, n) + c) % n;
        y = (mulmod(y, y, n) + c) % n;
        y = (mulmod(y, y, n) + c) % n;
        g = __gcd(abs(x - y), n);
        if (g == n) return pollard_rho(n);
    }
    return g;
}

map<ll, int> factors;
void factorize(ll n) {
    if (n == 1) return;
    if (isPrime(n)) {
        factors[n]++;
        return;
    }
    ll d = pollard_rho(n);
    factorize(d);
    factorize(n / d);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    if (cin >> n) {
        factorize(n);
        for (auto const& [p, exp] : factors) {
            cout << p << " " << exp << "\n";
        }
    }
    return 0;
}
  • Time Complexity: O(n^{1/4})
  • Space Complexity: O(log n)

Đây là thuật toán chuẩn để phân tích số lớn. Nó kết hợp hai phần:

  1. Miller-Rabin: Thử Fermat để kiểm tra tính nguyên tố một cách xác suất. Nó rất nhanh và chính xác cao cho các số lớn.
  2. Pollard's Rho: Một thuật toán xác suất để tìm thừa số nguyên tố. Nó dùng hàm x{n+1} = (xn^2 + c) mod n và tính GCD của hiệu hai phần tử trong chu kỳ để tìm ước chung. Thuật toán này chia để trị: tìm một thừa số d bằng Pollard's Rho, gọi đệ quy cho d và n/d cho đến khi tất cả đều là số nguyên tố.
Cách Sử dụng thư viện chuẩn (C++17)
#include <iostream>
#include <map>
#include <numeric>
#include <cmath>

void factorize(long long n, std::map<long long, int>& factors) {
    if (n == 1) return;
    if (std::gcd(n, 2LL) == 2) {
        factors[2]++;
        factorize(n / 2, factors);
        return;
    }
    if (std::gcd(n, 3LL) == 3) {
        factors[3]++;
        factorize(n / 3, factors);
        return;
    }
    // Sử dụng Pollard's Rho nếu có (thư viện extern)
    // Ở đây minh họa logic chia nhỏ
    long long d = 2; // Placeholder
    // Logic thực tế cần implement Pollard's Rho hoặc Trial Division
}

int main() {
    long long n;
    std::cin >> n;
    std::map<long long, int> factors;
    // Trong C++17 có std::pollard_rho nhưng chỉ là draft, không phải chuẩn.
    // Code mẫu dưới đây sử dụng Trial Division tối ưu cho code ngắn.
    // Để xử lý 10^18 cần thuật toán mạnh hơn.

    // Code tối ưu hóa Trial Division:
    int cnt2 = 0;
    while (n % 2 == 0) { n /= 2; cnt2++; }
    if (cnt2) std::cout << 2 << " " << cnt2 << "\n";

    for (long long i = 3; i <= std::sqrt(n); i += 2) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { n /= i; cnt++; }
            std::cout << i << " " << cnt << "\n";
        }
    }
    if (n > 1) std::cout << n << " 1\n";

    return 0;
}
  • Time Complexity: O(sqrt(n))
  • Space Complexity: O(1)

Phương pháp này sử dụng các thư viện chuẩn của C++ (như std::gcd) và tối ưu hóa vòng lặp Trial Division (chỉ lặp qua số lẻ, dừng ở sqrt(n)). Tuy nhiên, giống như Approach 1, nó chỉ hiệu quả khi các thừa số nguyên tố của n đủ nhỏ. Với n = 10^18, nếu n là số nguyên tố, vòng lặp sẽ chạy quá lâu.

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

Cách tiếp cận Time Space Tên
1 O(sqrt(n)) O(1) Trial Division với tối ưu hóa
2 O(n^{1/4}) O(log n) Pollard's Rho và Miller-Rabin
3 O(sqrt(n)) O(1) Sử dụng thư viện chuẩn (C++17)

Bài học kinh nghiệm

  • Với n lên tới 10^18, Trial Division thông thường là không đủ. Cần các thuật toán phức tạp hơn như Pollard's Rho.
  • Miller-Rabin là phương pháp kiểm tra nguyên tố xác suất tốt nhất cho các số lớn trong lập trình thi đấu.
  • Việc nhân số lớn (tránh tràn số) khi tính lũy thừa hoặc nhân mod là bắt buộc, thường dùng __int128 hoặc thuật toán nhân từng bit.

Lỗi thường gặp

  • Tràn số khi tính toán bình phương hoặc nhân hai số lớn (vd: a * b % mod với a, b ~ 10^9). Phải dùng kỹ thuật nhân an toàn.
  • Vòng lặp trong Trial Division chạy đến sqrt(n) nhưng sqrt(10^18) là 10^9, quá lớn để chạy trong 1s. Cần dùng Pollard's Rho.
  • Quên trường hợp n sau khi chia hết các thừa số nhỏ còn lại là một số nguyên tố lớn (ví dụ: n = 2 * p, với p lớn).

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.