Hướng dẫn giải của Khóa số

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, yukino, sussyboy, orzitzzang

Hiểu bài toán

Cho số nguyên dương N (1 ≤ N ≤ 10^18). Yêu cầu tìm:

  1. K1: số lượng các ước nguyên tố của N (distinct prime factors).
  2. K2: tổng các ước nguyên tố của N. Ví dụ: N = 12, các ước nguyên tố là 2 và 3. Do đó K1 = 2, K2 = 2 + 3 = 5.

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

Cách Phân tích thừa số nguyên tố cơ bản
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

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

    vector<ll> prime_factors;

    // Xử lý trường hợp đặc biệt N = 1
    if (n == 1) {
        cout << "0 0" << endl;
        return 0;
    }

    // Chia hết cho 2
    while (n % 2 == 0) {
        if (prime_factors.empty() || prime_factors.back() != 2) {
            prime_factors.push_back(2);
        }
        n /= 2;
    }

    // Chia hết cho các số lẻ từ 3 đến sqrt(n)
    for (ll i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            if (prime_factors.empty() || prime_factors.back() != i) {
                prime_factors.push_back(i);
            }
            n /= i;
        }
    }

    // Nếu n còn lại là số nguyên tố > 2
    if (n > 1) {
        prime_factors.push_back(n);
    }

    ll k1 = prime_factors.size();
    ll k2 = 0;
    for (ll p : prime_factors) {
        k2 += p;
    }

    cout << k1 << " " << k2 << endl;
    return 0;
}
  • Time Complexity: O(√N)
  • Space Complexity: O(log N)

Phương pháp này thử chia N cho các số từ 2 đến √N. Nếu chia hết, ta biết đó là ước nguyên tố và thêm vào danh sách. Tuy nhiên, với N lên tới 10^18, √N ≈ 10^9, phương pháp này quá chậm (cần ~10^9 phép chia).

Cách Phân tích thừa số nguyên tố với sàng Eratosthenes
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

const int MAX = 1000005;
vector<int> primes;
bool is_prime[MAX];

void sieve() {
    fill(is_prime, is_prime + MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < MAX; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = 2 * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    sieve();

    ll n;
    cin >> n;

    vector<ll> distinct_primes;
    ll sum = 0;

    // Thử chia hết cho các số nguyên tố nhỏ
    for (int p : primes) {
        if (1LL * p * p > n) break;
        if (n % p == 0) {
            distinct_primes.push_back(p);
            sum += p;
            while (n % p == 0) {
                n /= p;
            }
        }
    }

    // Nếu n còn lại là số nguyên tố lớn
    if (n > 1) {
        distinct_primes.push_back(n);
        sum += n;
    }

    cout << distinct_primes.size() << " " << sum << endl;
    return 0;
}
  • Time Complexity: O(10^6 log log 10^6 + √N)
  • Space Complexity: O(10^6)

Sử dụng sàng Eratosthenes để tạo các số nguyên tố nhỏ (đến 10^6). Sau đó chia N cho các số nguyên tố này. Nếu sau khi chia hết các số nguyên tố nhỏ mà N vẫn lớn hơn 1, thì N đó là một số nguyên tố lớn. Phương pháp này nhanh hơn nhiều so với phương pháp cơ bản nhưng vẫn có thể chậm nếu N là tích của hai số nguyên tố lớn (ví dụ N = 10^18 + 31).

Cách Thuật toán Pollard's Rho
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

ull mul_mod(ull a, ull b, ull mod) {
    __int128 res = (__int128)a * b;
    return res % mod;
}

ull pow_mod(ull a, ull b, ull mod) {
    ull res = 1;
    while (b) {
        if (b & 1) res = mul_mod(res, a, mod);
        a = mul_mod(a, a, mod);
        b >>= 1;
    }
    return res;
}

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

    ull d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    static const ull bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (ull a : bases) {
        if (n <= a) break;
        ull x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = mul_mod(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

ull pollard_rho(ull n) {
    if (n % 2 == 0) return 2;
    ull x = rand() % (n - 2) + 2;
    ull y = x;
    ull c = rand() % (n - 1) + 1;
    ull d = 1;
    auto f = [&](ull x) { return (mul_mod(x, x, n) + c) % n; };
    while (d == 1) {
        x = f(x);
        y = f(f(y));
        d = __gcd(x > y ? x - y : y - x, n);
        if (d == n) return pollard_rho(n);
    }
    return d;
}

void factorize(ull n, vector<ull>& factors) {
    if (n == 1) return;
    if (miller_rabin(n)) {
        factors.push_back(n);
        return;
    }
    ull divisor = pollard_rho(n);
    factorize(divisor, factors);
    factorize(n / divisor, factors);
}

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

    vector<ull> factors;

    // Chia hết cho 2
    while (n % 2 == 0) {
        n /= 2;
    }

    if (n > 1) {
        factorize(n, factors);
    }

    // Thêm 2 vào factors nếu ban đầu n chia hết cho 2
    if (n != factors[0]) {
        factors.push_back(2);
    }

    sort(factors.begin(), factors.end());
    factors.erase(unique(factors.begin(), factors.end()), factors.end());

    ull sum = 0;
    for (ull p : factors) {
        sum += p;
    }

    cout << factors.size() << " " << sum << endl;

    return 0;
}
  • Time Complexity: O(N^{1/4} log N)
  • Space Complexity: O(log N)

Đây là thuật toán chuẩn để phân tích một số lớn thành các thừa số nguyên tố.

  1. Miller-Rabin: Kiểm tra tính nguyên tố của số lớn (xác suất sai số cực nhỏ).
  2. Pollard's Rho: Tìm một thừa số ước của số合数 (composite).
  3. Đệ quy: Phân tích số cho đến khi tất cả đều là số nguyên tố. Với N ≤ 10^18, thuật toán này chạy rất nhanh (thường dưới 1ms).

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

Cách tiếp cận Time Space Tên
1 O(√N) O(log N) Phân tích thừa số nguyên tố cơ bản
2 O(10^6 log log 10^6 + √N) O(10^6) Phân tích thừa số nguyên tố với sàng Eratosthenes
3 O(N^{1/4} log N) O(log N) Thuật toán Pollard's Rho

Bài học kinh nghiệm

  • Bài toán yêu cầu các ước nguyên tố phân biệt, không phải phân tích thừa số nguyên tố đầy đủ (ví dụ 12 = 2^2 * 3, ước nguyên tố là {2, 3}).
  • Với N lên tới 10^18, các phương pháp dựa trên vòng lặp từ 2 đến √N là không thể chấp nhận được.
  • Thuật toán Pollard's Rho kết hợp với Miller-Rabin là phương pháp hiệu quả nhất để phân tích số lớn trong lập trình thi đấu.

Lỗi thường gặp

  • Sử dụng biến int hoặc long (32-bit) thay vì long long (64-bit)导致 overflow khi tính toán với N ≤ 10^18.
  • Quên xử lý trường hợp N = 1 (không có ước nguyên tố).
  • Sử dụng phép chia và nhân trực tiếp trong modulus operator (a * b % mod) dẫn đến overflow, cần sử dụng __int128 hoặc thuật toán nhân chậm (binary multiplication).
  • Trong thuật toán Pollard's Rho, nếu không kiểm soát tốt hàm ngẫu nhiên hoặc hàm lặp, có thể陷入 vòng lặp vô hạn hoặc trả về sai thừa số.

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.