Editorial for 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: Yunan

Subtask 1: Ta đơn giản kiểm tra tất cả các bộ ba $(i,j,k)$ ~(i,j,k)~.

Độ phức tạp: $O(|L-R|^3)$ ~O(|L-R|^3)~

Subtask 2: Ta tiến hành đếm số bộ ba $(i,j,k)$ ~(i,j,k)~ thỏa mãn $LCM(i,j,k)<i+j+k$ ~LCM(i,j,k)<i+j+k~.

Vì $LCM(i,j,k) \in \{k,2k,3k,4k,...\}$ ~LCM(i,j,k) \in \{k,2k,3k,4k,...\}~ và $i<j<k$ ~i<j<k~ nên ta cần đếm số bộ ba thỏa mãn một trong hai trường hợp:

Trường hợp 1: $LCM(i,j,k)=k$ ~LCM(i,j,k)=k~
Trường hợp 2: $LCM(i,j,k)=2k$ ~LCM(i,j,k)=2k~ và $i+j>k$ ~i+j>k~

Đối với trường hợp 1, ta đơn giản đếm số ước $d$ ~d~ của $k$ ~k~ $(L+2 \le k \le R)$ ~(L+2 \le k \le R)~ thỏa mãn $L \le d < k$ ~L \le d < k~. Gọi số lượng ước $d$ ~d~ tìm được là $cnt$ ~cnt~, khi đó số lượng bộ ba $(i,j,k)$ ~(i,j,k)~ thỏa mãn $LCM(i,j,k)<i+j+k$ ~LCM(i,j,k)<i+j+k~ thuộc về trường hợp 1 là:

$(cnt-1)+(cnt-2)+...+2+1=\frac{cnt(cnt-1)}{2}$

Đối với trường hợp 2, vì $i+j>k$ ~i+j>k~ và $i<j<k$ ~i<j<k~ nên $j>\frac{k}{2}$ ~j>\frac{k}{2}~. Ngoài ra, $j$ ~j~ là ước số của $2k$ ~2k~ nên $j \in \{\frac{2k}{3},\frac{2k}{2},\frac{2k}{1}\}$ . Từ đó, dễ dàng nhận thấy $j=\frac{2k}{3}$ ~j=\frac{2k}{3}~ và $\frac{k}{3}<i<\frac{2k}{3}$ ~\frac{k}{3}<i<\frac{2k}{3}~. Vì $i$ ~i~ cũng là ước số của $2k$ ~2k~ nên $i=\frac{2k}{5}$ ~i=\frac{2k}{5}~ hoặc $i=\frac{2k}{4}$ ~i=\frac{2k}{4}~.

Tóm lại đối với trường hợp 2, ta chỉ cần kiểm tra: $(i,j)=(\frac{2k}{5},\frac{2k}{3})$ ~(i,j)=(\frac{2k}{5},\frac{2k}{3})~ hoặc $(i,j)=(\frac{2k}{4},\frac{2k}{3})$ ~(i,j)=(\frac{2k}{4},\frac{2k}{3})~.

Độ phức tạp: $O(R\sqrt{R})$ ~O(R\sqrt{R})~

Subtask 3: Gọi $count_{i,k}$ ~count_{i,k}~ của đoạn $[i,k]$ ~[i,k]~ là số lượng số nguyên $j$ ~j~ thỏa mãn $i<j<k$ ~i<j<k~ và $LCM(i,j,k)<i+j+k$ ~LCM(i,j,k)<i+j+k~. Khi đó, tổng số lượng bộ ba $(i,j,k)$ ~(i,j,k)~ thỏa mãn $LCM(i,j,k)<i+j+k$ ~LCM(i,j,k)<i+j+k~ là $\sum count_{i,k}$ ~\sum count_{i,k}~ với $L \le i < k \le R$ ~L \le i < k \le R~ $($ ~(~tổng các giá trị $count_{i,k}$ ~count_{i,k}~ của các đoạn $[i,k]$ ~[i,k]~ nằm trong $[L,R]$ ~[L,R]~ $)$ ~)~.

Từ đó, ta có thể tính $count_{i,k}$ ~count_{i,k}~ cho từng đoạn $[i,k]$ ~[i,k]~ và với mỗi test case, tính tổng các giá trị $count_{i,k}$ ~count_{i,k}~ của các đoạn $[i,k]$ ~[i,k]~ nằm trong đoạn $[L,R]$ ~[L,R]~.

Độ phức tạp: $O(T.R.R^{\frac{1}{3}})$ ~O(T.R.R^{\frac{1}{3}})~

Subtask 4: Ta có thể xử lý các test case dưới dạng offline:

Xây dựng mảng $A$ ~A~, ban đầu $A_k=0$ ~A_k=0~ với mọi $3 \le k \le 10^5$ ~3 \le k \le 10^5~.
Duyệt qua các giá trị $i$ ~i~ giảm từ $99998$ ~99998~ về $1$ ~1~.
Với mỗi giá trị $i$ ~i~, cập nhật $A_k=A_k+count_{i,k}$ ~A_k=A_k+count_{i,k}~ với mỗi đoạn $[i,k]$ ~[i,k]~.
Đồng thời với các đoạn $[L,R]$ ~[L,R]~ $(L=i)$ ~(L=i)~, số bộ ba $(i,j,k)$ ~(i,j,k)~ thỏa mãn $LCM(i,j,k)<i+j+k$ ~LCM(i,j,k)<i+j+k~ là $A_{l+2}+A_{l+3}+...+A_r$ ~A_{l+2}+A_{l+3}+...+A_r~.

Việc xây dựng mảng $A$ ~A~ có thể thực hiện bằng cấu trúc Segment Tree hoặc Fenwick Tree.

Độ phức tạp: $O((T+R).log(R))$ ~O((T+R).log(R))~

Editorial for LCM

Comments