Hướng dẫn giải của Vẫn là bội chung nhỏ nhấ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, HungTron, vudinhlong

Hiểu bài toán

Yêu cầu: Đếm số cặp số nguyên dương (x, y) sao cho LCM(x, y) bằng tích các số nguyên dương liên tiếp từ a đến b (tức là a × (a+1) × ... × b). Với a ≤ b và T ≤ 10 test cases. Phân tích:

  • Gọi N = a × (a+1) × ... × b.
  • Ta cần tìm số lượng cặp (x, y) sao cho BCNN(x, y) = N.
  • Phép chia hết và Bội chung nhỏ nhất (LCM) liên quan đến thừa số nguyên tố. LCM(x, y) = N có nghĩa là:
    1. VỚI MỌI NGUYÊN TỐ p, p^e là lũy thừa cao nhất của p trong N.
    2. Phải có ÍT NHẤT MỘT trong hai số x hoặc y chứa thừa số p^e (tức là max(lũy thừa p trong x, lũy thừa p trong y) = e).
    3. Cả x và y chỉ được chứa các thừa số nguyên tố có trong N, và với độ mũ không được vượt quá e.

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

Cách Phân tích thừa số nguyên tố (Prime Factorization)
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;

int minPrime[MAX];

// Sieve of Eratosthenes to find smallest prime factor
void sieve() {
    for (int i = 2; i < MAX; i++) {
        if (minPrime[i] == 0) {
            for (int j = i; j < MAX; j += i) {
                if (minPrime[j] == 0) minPrime[j] = i;
            }
        }
    }
}

// Function to multiply two numbers modulo MOD
int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

// Function to calculate a^b modulo MOD
int power(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

void solve() {
    int a, b;
    cin >> a >> b;

    // Map to store prime factors and their exponents in N = a * ... * b
    map<int, int> factors;

    // Factorize each number from a to b
    for (int i = a; i <= b; i++) {
        int x = i;
        while (x > 1) {
            int p = minPrime[x];
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt++;
            }
            factors[p] = max(factors[p], cnt);
        }
    }

    int ans = 1;
    // For each prime factor p with max exponent e in N
    // Number of ways to distribute p exponents between x and y such that max(e_x, e_y) = e
    // Total pairs of (e_x, e_y) where 0 <= e_x, e_y <= e: (e+1)^2
    // Pairs where max(e_x, e_y) < e (i.e., both <= e-1): e^2
    // Good pairs = (e+1)^2 - e^2 = 2e + 1
    // Total answer is product of (2e + 1) for all prime factors
    for (auto it : factors) {
        int e = it.second;
        ans = mul(ans, (2 * e + 1));
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
  • Time Complexity: O((b-a+1) * log b + T * P log P) ~ O(10^6 * log 10^6)
  • Space Complexity: O(MAX)

Hướng tiếp cận này dựa trên tính chất của LCM đối với thừa số nguyên tố.

  1. Ta tính N = a * (a+1) * ... * b. Thay vì tính N trực tiếp (sẽ rất lớn), ta chỉ cần tìm phân tích thừa số nguyên tố của N. Ta có thể làm điều này bằng cách phân tích từng số từ a đến b và cộng dồn số mũ của các nguyên tố.
  2. Với mỗi nguyên tố p có số mũ lớn nhất là e trong N, số mũ của p trong x (gọi là ex) và trong y (gọi là ey) phải thỏa mãn max(ex, ey) = e.
  3. Với mỗi p, số lượng cặp (ex, ey) thỏa mãn là (2e + 1).
  4. Vì các nguyên tố phân biệt, tổng số cặp (x, y) là tích của (2e + 1) cho mọi p.
  5. Độ phức tạp đến từ việc phân tích số học (sàng nguyên tố nhỏ nhất và vòng lặp từ a đến b).
Cách Hash Map Optimization
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MXN = 1e6 + 7;

int mpf[MXN]; // min prime factor

void sang(int lim) {
    for (int i = 2; i <= lim; i++) {
        if (mpf[i] == 0) {
            for (int j = i; j <= lim; j += i) {
                if (mpf[j] == 0) mpf[j] = i;
            }
        }
    }
}

inline int mul(int a, int b) {
    return (1LL * a * b) % MOD;
}

void solve() {
    int a, b;
    cin >> a >> b;

    // Use unordered_map for faster average access
    unordered_map<int, int> factors;

    for (int i = a; i <= b; i++) {
        int x = i;
        while (x > 1) {
            int p = mpf[x];
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt++;
            }
            // Update max exponent for prime p
            if (cnt > factors[p]) {
                factors[p] = cnt;
            }
        }
    }

    int ans = 1;
    for (auto it : factors) {
        int e = it.second;
        ans = mul(ans, (2 * e + 1));
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sang(MXN - 1);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}
  • Time Complexity: O((b-a+1) * log b) (trung bình)
  • Space Complexity: O(K) với K là số lượng số nguyên tố xuất hiện

Đây là phiên bản tối ưu化的 của phương pháp phân tích thừa số nguyên tố.

  • Sử dụng unordered_map thay vì map để giảm thời gian truy cập và chèn.
  • Sàng trước mảng mpf (smallest prime factor) giúp quá trình phân tích số nhanh hơn (chỉ cần chia liên tục cho mpf[x]).
  • Logic tính toán tương tự: tìm phân tích thừa số của N, sau đó nhân (2e+1) cho mỗi thừa số.
  • Phương pháp này hiệu quả về mặt thời gian chạy thực tế cho giới hạn b-a <= 10^6.
Cách Optimization using Segment Tree / Sparse Table
// Note: This approach is overkill for this specific problem constraints (b-a small)
// but represents the most optimal way to query max exponent in range [a, b] for each prime.
// Since N = a * ... * b, we need max exponent in range.
// However, since we need to iterate numbers a to b anyway to find factors, 
// the standard factorization approach is usually preferred.
// 
// An alternative optimal approach for larger ranges (if we had precomputed prime lists) 
// is to iterate over primes p <= b.
// For each prime p, find max exponent e such that p^e divides some number in [a, b].
// 
// Algorithm:
// 1. Sieve primes up to b.
// 2. For each prime p:
//    Calculate the highest power of p, say p^k <= b.
//    Check if there is a multiple of p^k in [a, b]. If yes, e = k.
//    If not, check p^(k-1), etc.
// 3. Multiply (2e + 1).

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

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;

vector<int> primes;
bool isPrime[MAX];

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

int mul(int a, int b) { return (1LL * a * b) % MOD; }

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    sieve();
    int T; cin >> T;
    while (T--) {
        int a, b; cin >> a >> b;
        int ans = 1;
        for (int p : primes) {
            if (p > b) break;

            // Find max exponent e for prime p in range [a, b]
            // We need to find max e such that there exists x in [a, b] with p^e | x
            // This is equivalent to: max e such that floor(b / p^e) > floor((a-1) / p^e)

            long long curr = p;
            int exponent = 0;
            while (curr <= b) {
                // Check if there is a multiple of curr in [a, b]
                // i.e., ceil(a / curr) * curr <= b
                // or (a + curr - 1) / curr * curr <= b
                // Or simply: if (b / curr > (a - 1) / curr) 
                // Note: Be careful with integer division for (a-1)/curr if curr is large

                if (b / curr > (a - 1) / curr) {
                    exponent++;
                } else {
                    break; // If curr doesn't work, higher powers won't either because interval length < p^e
                }

                if (curr > b / p) break; // Avoid overflow
                curr *= p;
            }

            if (exponent > 0) {
                ans = mul(ans, (2 * exponent + 1));
            }
        }
        cout << ans << "\n";
    }
    return 0;
}
  • Time Complexity: O(T * (b log b / log b + (b-a+1) factor check)? No, O(T * P_prime(b) * log b) )
  • Space Complexity: O(MAX)

Phương pháp này tinh vi hơn. Thay vì phân tích từng số từ a đến b, nó lặp qua tất cả các số nguyên tố p <= b. Với mỗi p, nó tìm số mũ cao nhất e sao cho p^e chia hết cho một số nào đó trong đoạn [a, b]. Cách kiểm tra: p^e chia hết cho một số trong [a, b] nếu và chỉ nếu số lượng bội của p^e trong [a, b] > 0. Số lượng bội = floor(b / p^e) - floor((a-1) / p^e). Nếu > 0, thì e hợp lệ. Ta tìm e lớn nhất. Phương pháp này hữu ích nếu khoảng cách b-a rất lớn (ví dụ 10^9) nhưng b nhỏ, hoặc khi ta đã có sẵn danh sách số nguyên tố. Với b-a <= 10^6, phương pháp phân tích trực tiếp thường nhanh hơn.

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

Cách tiếp cận Time Space Tên
1 O((b-a+1) * log b + T * P log P) ~ O(10^6 * log 10^6) O(MAX) Phân tích thừa số nguyên tố (Prime Factorization)
2 O((b-a+1) * log b) (trung bình) O(K) với K là số lượng số nguyên tố xuất hiện Hash Map Optimization
3 O(T * (b log b / log b + (b-a+1) factor check)? No, O(T * P_prime(b) * log b) ) O(MAX) Optimization using Segment Tree / Sparse Table

Bài học kinh nghiệm

  • Vấn đề có thể được chia nhỏ thành các bài toán độc lập về thừa số nguyên tố nhờ tính chất của LCM: LCM(x, y) = N <=> Với mọi nguyên tố p, max(vp(x), vp(y)) = v_p(N).
  • Số cặp (ex, ey) thỏa mãn max(ex, ey) = e là (e+1)^2 - e^2 = 2e + 1.
  • Mặc dù N có thể rất lớn, ta chỉ cần quan tâm đến các thừa số nguyên tố của các số trong dãy từ a đến b.
  • Sử dụng Sàng Eratosthenes để tìm ước nguyên tố nhỏ nhất (min prime factor) giúp phân tích số nhanh chóng O(log n).

Lỗi thường gặp

  • Tràn số nguyên (Overflow): Tích các số từ a đến b có thể vượt quá 64-bit. Không tính N trực tiếp.
  • Sai số khi tính số mũ: Cần phải dùng vòng lặp chia hết để đếm chính xác số mũ của p trong từng số, và cập nhật max.
  • Hiệu năng: Dùng map thay vì unordered_map có thể gây chậm hơn. Dùng vector thay vì unordered_map nếu các chỉ số nguyên tố nhỏ và liên tục là tối ưu nhất (vì chỉ số là số nguyên tố, nhưng số nguyên tố thưa). Tuy nhiên unordered_map là lựa chọn tốt cho bộ nhớ chấp nhận được.
  • Xử lý số mũ 0: Nếu một số nguyên tố p có số mũ max là 0 (không xuất hiện), không được nhân 0 vào kết quả. Tuy nhiên trong logic duyệt từ a đến b, ta chỉ cập nhật khi có số mũ > 0.

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.