Editorial for Bedao Grand Contest 11 - K-ONLY


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.

Gọi ~f(x, y, k)~ là tổng các tích ~i \times j~ của các cặp ~i, j~ thỏa ~i \leq x, j \leq y~ và ~gcd(i, j) = k~.

Vậy đáp án cho bài toán là ~f(b, d, k) - f(a - 1, d, k) - f(b, c - 1, k) + f(a - 1, c - 1, k)~

Ta có ~f(x, y, k) = f(x / k, y / k, 1) \times k^2~, bài toán chuyển về tính ~f(x, y, 1)~.

Công thức tính ~f(x, y, 1)~ như sau:

~f(x, y, 1) = \displaystyle\sum_{k = 1}^{min(x, y)}{ g(x / k, y / k) \times mo[k] \times k^2 } ~, trong đó, ~mo~ là hàm mobius, ~g(a, b)~ là tổng các tích ~i \times j~ của các cặp ~i, j~ mà ~i \leq a, j \leq b~, ta có ~g(a, b) = (a \times (a + 1) / 2) \times (b \times (b + 1) / 2)~.

Nhận xét rằng, có thể chia đoạn ~[1;min(x, y)]~ thành khoảng ~\sqrt{min(x, y)}~ đoạn ~[l; r]~ mà ~x / k~ không đổi và ~y / k~ không đổi với mọi ~k~ thuộc đoạn ~[l;r]~.

Với mỗi đoạn ~[l;r]~ như vậy, ta có ~\displaystyle\sum_{k = l}^{r}{ g(x / k, y / k) \times mo[k] \times k^2 = g(x / l, y / l) \times \displaystyle\sum_{k = l}^{r}{mo[k] \times k^2} } ~, phần ~(\displaystyle\sum_{k = l}^{r}{mo[k] \times k^2})~ có thể được tính trong ~O(1)~ bằng cách tạo trước mảng tổng tiền tố của hàm ~mo[k] \times k^2 ~.

Vậy mỗi đoạn ~[l; r]~ chỉ cần ~O(1)~ để tính toán, độ phức tạp cho mỗi bộ dữ liệu là ~O(\sqrt{min(b/k, d/k)})~ hay ~O(\sqrt{min(b, d)})~, tổng độ phức tạp là ~O(q\sqrt{b})~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.