Editorial for Bedao Regular Contest 04 - LOG LCM


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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}~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.