题解 CF516E 【Drazil and His Happy Friends】

· · 题解

令 d = \gcd(m, n)，则可以发现，每一天，只有编号对 d 取余相同的一对男女生会一起玩。

也就是说，编号模 d 不同余的两人永远不会产生直接或间接关系，可以分开考虑。

那么就分成了 d 个子问题，第 i（0 \le i < d）个子问题包含所有 (x \bmod d) =i 的编号为 x 的人。

算出第 i 个子问题的答案之后，乘以 d 再加上 i 就能得到原问题的这个部分的答案，所有答案取 \max 即可。

由裴蜀定理，只要子问题中有一个人是快乐的，那么最终这个子问题中的所有人都会变得快乐。

特别地，如果 d > g + b，则因为至少存在一个子问题没有快乐的人，所以原问题无解。

这样就帮我们排除掉了 d 太大的情况，现在 1 \le d \le 2 \times {10}^5。

那么我们让 m, n 都除掉 d，只需要考虑这个子问题，注意此时 m, n 互质。

需要注意的是，如果所有人一开始就是快乐的（子问题可能存在此情况），请返回 -1 而不是 0，要不然会出错。

而如果所有人都不是快乐的，请返回无解。否则就考虑一般情况：

我们考虑单独计算最后一个女生变快乐的天数和最后一个男生变快乐的天数，取 \max 得到答案。

假设最后一个变快乐的女生是 i 号，那么她一定是在第 x 天变快乐的，满足 (x \bmod m) = i。

假设是因为 j 号男生变快乐的，这里 j = (x \bmod n)，那么就需要考虑 j 号男生是什么时候变快乐的。

如果 j 号男生一开始就是快乐的，那么显然他会在第 j 天让 (j \bmod m) 号女生变快乐。

令 c = (x - j) / n，也就是从他让 (j \bmod m) 号女生变快乐，直到他让 i 号女生变快乐之间经过的轮数。

则我们考虑在第 (j + n) 天，这个男生会让 ((j + n) \bmod m) 号女生变快乐。

一直到第 (j + c n) 天，也就是第 x 天，他会让 ((j + c n) \bmod m) 号女生，也就是 i 号女生变快乐。

那么我们是不是可以说，是 \boldsymbol{(j \bmod m)} 号女生，在经过 \boldsymbol{c} 轮（\boldsymbol{c n} 天）之后，让 \boldsymbol{((j + cn) \bmod m)} 号女生，也就是 \boldsymbol{i} 号女生变快乐的。

或者简化地说，如果 \boldsymbol{k} 号女生变快乐了，那么在 \boldsymbol{n} 天之后，\boldsymbol{((k + n) \bmod m)} 号女生一定会变快乐。

反复利用这个简化的结论 c 次，就可以推出 c n 天之后让 ((k + cn) \bmod m) 号女生变快乐的结论。

也就是说，对于每个女生 k，连一条从 k 出发，到达 ((k + n) \bmod m) 的边，边权为 n。

然后，对于每个一开始就是快乐的男生 j，从源点 S 连一条到达 (j \bmod m) 的边，边权为 j。

最后，对于每个一开始就是快乐的女生 i，从源点 S 连一条到达 i 的边，边权为 i。

求出 S 到每个点的最短路，对于一个一开始不是快乐的女生，S 到她的最短距离就会对答案产生贡献。

注意，对于一个一开始就是快乐的女生，不产生贡献，因为她并不是在第 i 轮才变快乐的，而是从一而终都快乐。

但是总点数是 {10}^9 级别的，没法做。

注意到第一类边很有特点，把所有女生连成了一个大环。

但是环上的点是每次 x \to ((x + n) \bmod m) 的，不按顺序。

我们用某种方式把这些点重标号，然后注意到只需要考虑二三类边中，与 S 相连的关键点即可。

把这些关键点按照在环上的顺序排序，就可以快速处理最短路了。

以上是对女生的考虑，如果是男生同理，只要转换一下就行。

时间复杂度为 \mathcal O ((b + g) \log (b + g))，评测链接。