https://www.luogu.com.cn/problem/P17802
考虑 \(\gcd(f_i,f_j)=f_{\gcd(i,j)}\)，可以用 min-max 容斥处理。
具体的：\(\sum_{s\ne \varnothing} f_{\gcd(s)}^{(-1)^{|s|+1}}\)。
处理答案的增量，也就是 \(\max s=i\) 的贡献。
考虑 \(\gcd=g\)，拉出以前所有 \(g\) 倍数的个数 \(c\)，贡献为 \(\sum_{j} \binom{c}{j}(-1)^j=[c=0]\)。
然后做倍数差分即可。
复杂度 \(O(n\mathrm{d}(V)\omega(V))\)，其中 \(\omega\) 表示最多不同质因子个数。
实际上跑不满。
要手写哈希表。