CF516E

· · 题解

有 n 个男生和 m 个女生，分别标号为 [0,n) 与 [0,m)。初始有一些人有 HIV，在第 i 天（从 0 开始）男生 i \bmod n 与女生 i \bmod m 如果其中一个有 HIV，那么另外一个也会得上 HIV。问最少多少天之后所有人都会得上 HIV，或者最后总有一个人会幸免于难。

令 g=\gcd(n,m)，则只有 \bmod g 相同的两个人才会及逆行传染，称两个人在一组。于是有人能幸免于难当且仅当有一个组没有 HIV 患者。否则所有组都是独立的，每个组的结果都是容易合并的。下面令 n 与 m 互质。

研究传播问题的一个方法就是对传播关系建图，即令 (u,v) 表示当 u 被传染之后，其会把病毒传染给 v。由于我们需要研究最短传染时间，所以可以考虑在加一个边权 w：(u,v,w) 表示当 u 在被传染之后 w 时会把病毒传染给 v。目标是通过某些点的多源最短路反映所有人被传染的时间。

但是这图也挺不好建的：对于一个男生 i，其被 j 传染之后，会在 n 时刻后传染给 (j+n) \bmod m 号女生。于是我们可以粗略的建立一张图：令 (i,j) 点代表 j 被 i 传染过一次，我们考虑将 (B_i,G_j) 连边连向 (G_j,B_{{i+m} \bmod n})，边权为 m。另一侧同理。其中令 B_i 代表男生 i，G_j 代表女生 j。我们可以发现一个事实：在 B_i 传染过一个人之后，B_{i+m \bmod n} 会被传染。是不是意味着当 i 被感染之后，其在每 m 个时刻会向 B_{i+m \bmod n} 传染一次呢？

好的图建出来了。但是男生与女生之间的传播是不是被忘了？如果把边加进来的话，那么发现这个性质有什么意义呢？能不能通过性质边把原本的点与边剪一剪？

距离答案已经很接近了。可以发现性质所建出来的图已经完美描摹了同性之间的间接传播，即非零号病人直接传播的传播。那么异性之间的间接传播呢？我们得知道什么是间接传播：在 B_i 传播给 G_j 之后，其传播给 B_{i+m \mod n}，然后再传播给 G_{k} \dots 停停停，其完全可以认为是 B_i 向 B_{(i+m) \bmod n} 传播，G_j 向 G_k 传播。那么我们只需要管的是直接传播，即从零号病人出发的直接传播，即第一次传播。可以发现最多只有 O(n) 条传递关系。

于是就可以建图了：连接 (B_i,B_{i+m \bmod n},m)(G_i,G_{i+n} \bmod m,n)(B_{i},G_{i \bmod m},i)(G_i,B_{i \bmod n},i)。其中后两种边的 i 为零号病人。发现我们的关键点只有零号病人，被零号病人传染的人以及零号病人在环前面的一个人。一共只有 O(n) 个点。

现在的问题只有一个：如何得到环上若干个点的相对顺序？这个也很简单，我们可以通过解同余方程的方法得到环上这些点是环上的第几个点。

于是跑个最短路就完了。