Codeforces Round 911 (Div. 2)

https://codeforces.com/contest/1900

D. Small GCD

题意

定义 $f(x,y,z)$ 为 $x,y,z$ 中较小两数的 $\gcd$。给定数组 $a$ ，求所有三元组的 $f$ 之和。

数据范围：$3\leq n\leq 8\times10^4,1\leq a_i\leq10^5$。

题解

给 $a$ 排序，依次枚举。我们维护当前所有数的二元组 $\gcd$ 之和，当前枚举到的数是最大数，它的贡献就是维护的这个值。

我们考虑如何维护这个值：这是一个经典的问题。我们维护 $cnt_i$ 表示 $i$ 的倍数有多少个。对于当前的数 $x$，我们从大到小枚举因子 $y$。设 $\gcd(x,a_i)=y$ 的 $a_i$ 的数量为 $f_y$，那么有 $f_y=cnt_y-\sum\limits_{k\geq2}f_{ky}$。后面减的部分可以在每次处理完 $y$ 后对因子减去贡献。

E. Transitive Graph

题意

给出一个图,要求图的传递闭包中点权和最小的简单最长路。

题解

可以用强连通分量缩点,可以发现每个强连通分量在传递闭包中是一个完全图,因为我们需要的是最长路所以只要走到这个强连通分量就必须走完分量中的所有点。

然后跑个DAG上的DP就好了。