Editorial for Bedao Regular Contest 09 - DISTINCT


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 cùng tìm hiểu về công thức tính ~f(B)~ từ dãy con ~B~ bất kỳ.

Nhận xét 1: Điều kiện điểm ~(x, y)~ thuộc đường thẳng đi qua ~(B_i, 0)~ và ~(0, B_i)~ tương đương với ~x+y = B_i~

Nhận xét 2: Số lượng lattice point nằm trên đoạn thẳng nối ~(0,0)~ với ~(x, y)~ (~x, y~ nguyên dương) là ~gcd(x, y)~.

Nhận xét 3: Nếu cặp số nguyên dương ~(x, y)~ thỏa mãn ~x+y = B_i~ thì ~gcd(x, y) < B_i~ và ~gcd(x, y)~ phải là một ước của ~B_i~

Nhận xét 4 : Nếu gọi ~p_i~ là ước nguyên tố bé nhất của ~B_i~ thì có đúng ~(p_i-1)~ cách để chọn ra cặp số ~(x, y)~ sao cho ~x+y = B_i~ và ~gcd(x, y)~ là ước lớn thứ 2 của ~B_i~. Mặt khác, từ nhận xét 3 có thể kết luận rằng ~gcd(x, y)~ lớn nhất chính bằng ước lớn thứ 2 của ~B_i~.

Theo nhận xét 1 và 2, dễ thấy ~f(B)~ là số cách chọn ~m~ cặp số nguyên dương sao cho cặp thứ số ~i~ là ~(x_i, y_i)~ thỏa mãn ~x_i+y_i = B_i~ với ~gcd(x_i, y_i)~ lớn nhất có thể. Vậy từ nhận xét 4 ta rút ra được công thức ~f(B[1 \dots m]) = \prod_{i = 1}^{m} (p_i - 1)~.

  • Sau đó, hãy tìm công thức tính ~s(A)~ với mảng ~A~ bất kỳ.

Theo định nghĩa thì ~s(A) = \sum_{B \in A, B \neq \emptyset} f(B)~ nhưng ta sẽ đơn giản hóa công thức này bằng toán tổ hợp. Với mỗi phần tử ~A_i~ có hai trường hợp xảy ra, một là ~A_i~ nằm ngoài dãy con ~B~ được chọn, hai là ~A_i~ nằm trong dãy con ~B~ và trường hợp này có ~(p_i-1)~ ~(p_i~ là ước nguyên tố bé nhất của ~A_i)~ cách chọn cặp số ~(x_i, y_i)~ sao cho ~x_i+y_i=A_i~ với ~gcd(x_i, y_i)~ lớn nhất. Vậy mỗi phần tử ~A_i~ có ~(p_i-1+1) = p_i~ cấu hình phù hợp, suy ra ~s(A) = -1 + \prod_{i = 1}^{n} p_i~ tương đương ~s(A)+1 = \prod_{i = 1}^{n} p_i~.

Chú ý : Ta cần cộng ~1~ vào vế trái để loại trừ trường hợp ~B~ là dãy con rỗng, ngoài ra lúc này vế phải của đẳng thức là tích các số nguyên tố nên bài toán đã đơn giản hơn rất nhiều.

  • Gọi mảng ~A~ sau khi xóa là ~A'~, cho truy vấn ~[L, R]~, ta cần đếm số giá trị khác nhau của ~s(A')~ với ~A'~ là một dãy con của ~A[L\dots R]~.

Ta có: ~s(A[L \dots R]) + 1 = \prod_{i = L}^{R} p_i~.

Dễ thấy nếu ~A'~ là một dãy không rỗng của ~A[L\dots R]~ thì ~s(A')+1 ~ sẽ là một ước của ~s(A[L\dots R]) + 1~. Mặt khác, hiển nhiên tồn tại ít nhất một dãy con ~A'~ ứng với mỗi ước của ~s(A[L\dots R]) + 1~ hay ước của ~\prod_{I = L}^{R} p_i~. Vì vậy ta chỉ cần đếm số ước của ~\prod_{I = L}^{R} p_i~ là ra số giá trị phân biệt của ~s(A')~. Công việc này có thể thực hiện bằng cách đếm số lần xuất hiện của từng số nguyên tố trong ~\prod_{I = L}^{R} p_i~. Đáp án cuối cùng sẽ là ~-1 + \prod (cnt_i + 1)~ với ~cnt_i~ là số lần xuất hiện của số nguyên tố thứ ~i~ ở trong đoạn ~p[L\dots R]~ ~(-1~ là để loại đi trường ~A'~ là dãy con rỗng~)~.

Ta sẽ sử dụng thuật toán Mo để duy trì mảng đếm ~cnt_i~ (số lần xuất hiện của số nguyên tố thứ ~i~ trong đoạn đang xét). Do các số nguyên tố có thể rất lớn nên cần nén số các số nguyên tố lại.

  • Tính ~p_i~ bằng cách sử dụng sàng nguyên tố trên đoạn (do ~max(A) - min(A) \le 10^7~). Ta có thể tăng tốc tính toán bằng cách dùng nhận xét ~A_i \le 10^{12}~ suy ra nếu ~p_i > \sqrt{10^{12}} = 10^6~ thì ~A_i = p_i~ (Vì ~p_i~ là ước nguyên tố bé nhất, nếu có ước nguyên tố khác ~ > p_i~ thì rõ ràng khiến ~A_i > 10^{12}~). Nén các ~p_i~ tìm được theo thứ tự từ ~1~ trở đi để thuận tiện sử dụng mảng đếm ~cnt~ thông thường.

Chú ý : sử dụng phép chia dư cho ~10^9 + 7~ ở bước tính kết quả một cách cẩn thận.

Độ phức tạp: ~O((N + Q) \sqrt{N})~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.