Hướng dẫn giải của Bedao Regular Contest 04 - LOG LCM


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.

Tác giả: bedao

Đầu tiên ta sẽ giải bài toán với truy vấn dạng ~L\,R~ để suy ra lời giải cho truy vấn dạng ~k\,R~.

Biểu diễn các số trong đoạn ~a[L \ldots R]~ dưới dạng tích của thừa số nguyên tố.
Giả sử ~p[1 \ldots k]~ là tập hợp các thừa số nguyên tố nằm trong biểu diễn của ít nhất 1 số thuộc ~a[L \ldots R]~.
Giả sử có mảng ~m[1 \ldots k]~ lưu thông tin sau:

  • ~m[1]~ là số mũ to nhất của ~p[1]~
  • ~m[2]~ là số mũ to nhất của ~p[2]~
  • ~\ldots~
  • ~m[k]~ là số mũ to nhất của ~p[k]~

~\rightarrow~ ~LCM(a[L \ldots R]) = p[1]^{m[1]} \ldots p[k]^{m[k]}~.

Vậy số các ~x~ thỏa mãn ~log_x(LCM(a[L \ldots R]))~ là số nguyên dương là một ước chung của ~m[1 \ldots k]~ ~\leftrightarrow~ số ước của ~gcd(m[1 \ldots k])~.

~\rightarrow~ Bài toán quay về tính ~gcd(m[1 \ldots k])~.

Nhận xét: nếu tồn tại ~i \in [1, k]~ sao ~p[i] > \sqrt{4e6}~ thì hiển nhiên ~m[i] = 1 \rightarrow gcd(m[1 \ldots k]) = 1~. Ta có thể xây mảng tổng tiền tố để kiểm tra các đoạn ~[L, R]~ chứa thừa số nguyên tố ~> \sqrt{4e6}~ trong ~O(1)~, ta chỉ quan tâm đến thừa số nguyên tố ~\le \sqrt{4e6} = 2000~ ~\rightarrow~ Có tối đa ~303~ số nguyên tố phải xét.

Ta có thể giải bài toán offline như sau: chạy ~i~ từ ~1 \rightarrow n~, duy trì một lookup table ~2~ chiều ~f[1..2000][1..21]~ với ~f[p][m]~ là vị trí của phần tử gần nhất với ~i~ sao cho biểu diễn của ~a[f[p][m]]~ chứa thừa số nguyên tố ~p~ với số mũ bằng ~m~, bằng cách duyệt qua hết ~303~ số nguyên tố này ta trả lời được các query mà đoạn ~[L, R]~ có ~R = i~.

Ta có thể tính ra rằng, ~\sum_p \log_p(4e6) = 696~ với ~p~ là các số nguyên tố ~\le 2000~.

Để có thể giải được truy vấn dạng ~k\,R~, ta có thử sử dụng một cấu trúc dữ liệu linked list để lưu lại tất cả ~696~ vị trí thay đổi này. Dễ thấy với mỗi số nguyên tố, ta có thể lưu các vị trí thay đổi chúng như một cái stack tăng dần. Vì vậy ta chỉ thêm vị trí thay đổi ở cuối đoạn hoặc xóa vị trí thay đổi ở trong đoạn ~\rightarrow~ có thể sử dụng linked list. Giả sử các vị trí thay đổi là ~v_1, v_2, \ldots, v_k~ ta có thể thấy đáp án các truy vấn ~L\,R~ với ~v_{k - 1} < L < v_k~ là như nhau, tương tự với các truy vấn ~L\,R~ với ~v_{k - 2} < L < v_{k - 1}, \ldots, v_1 < L < v_2~.

Vì vậy ta có thể tính đáp án cho từng khoảng và nhân lên với số lượng ~L~ tương ứng và nhận được đáp án.

Lưu ý: Tính lại gcd cho từng khoảng sẽ làm chương trình chạy quá thời gian, vậy nên cần tính trước tất cả gcd của tất cả tập hợp mũ có thể. Dễ thấy ~\log_2{4e6} < 22~, ta có thể lưu toàn bộ chúng bằng mảng bitmask có độ lớn ~2^{21}~.

Độ phức tạp thuật toán: ~O(a_{max} + n \times \log{(a_{max})} + n \times d(a_{max}) + q \times 696)~ với ~d(a_{max})~ là số ước nguyên tố tối đa của một số bé hơn hoặc bằng ~a_{max}~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int MAXA = 1e6 + 7, MAXN = 5e5 + 7;

int p[MAXA], a[MAXN], ans[MAXN], greaterSqrt = INT_MAX, order[MAXA], nearest[1000][28], s[MAXN];
vector <pair <int, int> > query[MAXN];
vector <int> prime;

void eratos()
{
    for (int i = 2; i * i <= 1000000; ++i)
        if (!p[i])
            for (int j = i * i; j <= 1000000; j += i)
                p[j] = i;

    int h = 0;
    for (int i = 2; i <= 1000000; ++i)
        if (!p[i]) 
        {
            p[i] = i;
            if (i <= 1000)
            {
                order[i] = ++h;
                prime.push_back(i);
            }
        }
    // cout << h;
}

void factor(int val, int pos)
{
    while (val > 1)
    {
        int k = p[val], cnt = 0;
        while (val % k == 0)
        {
            if (k > 1000) // SQRT(MAXA) = 1000
                greaterSqrt = pos;
            else
                ++cnt;
            val /= k;
        }

        if (k <= 1000) 
            nearest[order[k]][cnt] = pos;
    }
}

int main()
{

    eratos();
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) 
    {
        cin >> a[i];
        s[i] = s[i - 1] + (a[i] == 1 ? 1 : 2); // a[i] > 0
    }

    for (int i = 1, l, r; i <= q; ++i)
    {   
        cin >> l >> r;
        query[l].push_back({r, i});
    }

    for (int l = n; l > 0; --l)
    {
        factor(a[l], l);
        for (auto que: query[l])
        {
            int r = que.first, i = que.second;
            if (greaterSqrt <= r) ans[i] = 1;
            else if (s[r] - s[l - 1] == r - l + 1) ans[i] = 0;
            else
            {
                int gcd = 0;
                for (int j = 1, pw = 0; j <= 168; ++j)
                {
                    for (int k = 1, s = 1; s <= 1000000; ++k, s *= prime[j - 1])
                        if (nearest[j][k] <= r && nearest[j][k]) pw = k;

                    if (gcd) gcd = __gcd(gcd, pw);
                    else gcd = pw;
                }

                for (int j = 1; j <= gcd; ++j)
                    if (gcd % j == 0)
                        ++ans[i];
            }
        }
    }

    for (int i = 1; i <= q; ++i) cout << ans[i] << ' ';

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


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