根据唯一分解定理，令 \(x=p_1^{q_1}p_2^{q_2}\cdots p_m^{q_m},y=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\)，则 \(\text{lcm}(x,y)=p_1^{\max(q_1,k_1)}p_2^{\max(q_2,k_2)}\cdots p_m^{\max(q_m,k_m)}\)。那么一定存在 \(i\mid x,j\mid y\)，使得 \(\text{gcd}(i,j)=1\) 且 \(\text{lcm}(i,j)=\text{lcm}(x,y)\)，因为如果对每个 \(p_i\) 考虑的话，如果 \(q_i\ge k_i\)，把 \(p_i^{\max(q_i,k_i)}\) 给 \(i\)，否则给 \(j\) 即可。
令值域为 \(A\le 10^5\)。考虑到 \(a_i\le A\)，于是枚举 \(d\mid a_i\) 加入集合 \(S\)，即求 \(\max\limits_{x,y\in S}xy[\gcd(x,y)=1]\)，显然去重后 \(|S|\le A\)。
发现如果 \(x<y\) 且 \(\gcd(x,y)=1\)，那么 \(\forall x<z<y\)，\(xz<xy\)，所以 \(z\) 实际上对答案没有贡献。所以我们从大到小枚举 \(x\) 并加入一个栈中，如果加入栈之前里面有 \(\gcd(x,y)=1\) 的 \(y\)，那么我们从栈顶一直 pop 到 \(y\)，中间所有数都对答案没有贡献。\(y\) 对答案的贡献就是 \(xy\)。
如果我们知道栈里有与 \(x\) 互质的数就可以直接弹栈，均摊是 \(O(n)\) 的，考虑快速判断栈里有没有与 \(x\) 互质的数。
显然这样的数的个数是 \(f(x)=\sum\limits_{i=1}^{A}c_i[\gcd(i,x)=1]\)，\(c_i\) 表示栈中 \(i\) 这个数的个数，去重后为 \(0/1\)。然后就是 classical 的了：
\[\begin{aligned}f(x)&=\sum\limits_{i=1}^{A}c_i[\gcd(i,x)=1]\\&=\sum\limits_{i=1}^Ac_i\sum\limits_{d\mid i,d\mid x}\mu(d)\\&=\sum\limits_{d\mid x}\mu(d)\sum\limits_{d\mid i} c_i\end{aligned} \]令 \(t_d=\sum\limits_{d\mid i}c_i\) 为 \(d\) 的倍数在栈中的个数。
\[f(x)=\sum\limits_{d\mid x}\mu(d)t_d \]求一遍 \(f(x)\) 是 \(O(d(x))\) 的，弹栈的时候动态维护 \(f(x)\) 和 \(t_i\) 的值即可。复杂度 \(O(\sum\limits_{i=1}^Ad(i))=O(A\log A)\)。
如果没观察到一开始的那个性质，直接枚举 \(\gcd(x,y)\) 也可以做到 \(O(A\log^2 A)\)。
标签：CF1285F,gcd,limits,max,sum,mid,Classical,text From： https://www.cnblogs.com/Ender32k/p/17569340.html