题解 CF516E 【Drazil and His Happy Friends】

> [CF516E Drazil and His Happy Friends](https://codeforc.es/contest/516/problem/E) ## 题意 - 有 $n$ 个男生 $m$ 个女生，编号分别为 $0 \sim n - 1$ 和 $0 \sim m - 1$。 - 有 $b$ 个男生和 $g$ 个女生是快乐的，其他人是不快乐的。 - 在第 $i$ 天，编号为 $i \bmod n$ 的男生和编号为 $i \bmod m$ 的女生会一起玩。 - 如果他们俩中有一个人是快乐的，则另一个人也会变快乐。 - 求至少要多少天所有人都会变快乐，或者判断不可能所有人都变快乐。 - $n,m \le 10^9$，$b,g \le 10^5$。 ## 题解 首先考虑 $\gcd(n,m) \ne 1$，我们可以按照 $\bmod \gcd(n,m)$ 分组，不同组之间显然互不影响。 那么根据**裴蜀定理**，有解的充要条件为**每组内至少有一个人是快乐的**。 若有解，将每一组的答案求出来后取 $\max$ 即可。 考虑某一组，此时不妨设 $n > m$，同时有 $\gcd(n,m) = 1$。 首先有一个结论：**如果 $n$ 个男生都快乐了，那么除非当前天数小于 $m$，否则所有女生一定也都是快乐的。**这是因为往前的 $m$ 天里，由于所有男生都快乐了，因此要么是原本就都快乐，要么是快乐的影响另一个。 那么我们只需要求出最后一个变快乐的男生即可。为了方便，如果女生 $x$ 初始快乐，那么将男生 $x$ 也标记为初始快乐。 对于一个男生 $x$，若它在第 $t$ 天变快乐，那么他就会通过女生 $t \bmod m$ 在第 $t+m$ 天使男生 $(t+m)\bmod n$ 变快乐。 考虑**同余最短路**，则有连边 $i \stackrel{m}{\longrightarrow} (i+m)\bmod n$。另外，建立一个虚拟源点 $S$，对于初始快乐的男生 $i$，有连边 $S \stackrel{i}{\longrightarrow} i$。 则最后所有点的最短路的最大值就是这一组的答案。 但是这样点数是 $10^9$ 级别的，无法承受。 注意到这样的建图方式实际上会形成一个**环**，因此考虑删掉一些并不重要的点：如果 $i$ 和 $(i+m) \bmod n$ 初始都是不快乐的，那么 $i$ 一定会在 $(i+m) \bmod n$ 之前变快乐，因此 $i$ 就没用了。 那么我们可以只保留 $i$ 或 $(i+m) \bmod n$ 初始快乐的节点，这样点数只有 $10^5$ 级别了。 如何进行连边呢？ 设 $i$ 初始快乐的节点为 $A$ 类点，编号为 $A_i$；$(i+m) \bmod n$ 初始快乐的节点为 $B$ 类点，编号为 $B_i$。 我们要连三类边： 1. $S \stackrel{i}{\longrightarrow} A_i$ 2. $B_i \stackrel{m}{\longrightarrow} A_i$ 3. $A_i \stackrel{xm}{\longrightarrow} B_j$ 第 $1,2$ 类边都很容易，问题在第 $3$ 类边上。要求出 $B_j$，求出 $A_j$ 即可，那么此时实际上问题转化为**在模 $n$ 意义下以 $m$ 为跨度的有向环上，从每一个 $A_i$ 往后遇到的第一个 $A_j$ 是哪个**。 我们可以考虑 $i$ 最小的 $A_i$，求出从 $A_i$ 开始分别要经过多少个 $m$ 到达其他 $A$ 类点 $A_j$，即求 $i + xm \equiv j \pmod n$ 的最小非负整数解 $x$，使用 exgcd 即可。注意实现时其实只用求一次 exgcd。 求完后，对所有 $x$ 排序，即可求出**环上 $A$ 类点依次被经过的顺序**，也就求出了**每一个 $A_i$ 往后遇到的第一个 $A_j$ 是哪个**。 这样第 $3$ 类边也能够连上了。 注意最后还要特判天数小于 $m$ 的情况。 总时间复杂度 $\mathcal O(n \log n)$。 ## 代码 ```cpp #define Fail return print(-1), 0 const int N = 1e5 + 7; const ll inf = 0x3f3f3f3f3f3f3f3f; int n, m, d, B, G, b[N], g[N]; vi a[N<<1], f[N<<1]; ll ans; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int exgcd(int a, int b, int &x, int &y, int d = 0) { return b ? (d = exgcd(b, a % b, y, x), y -= a / b * x, d) : (x = 1, y = 0, a); } inline ll solve(vi a, vi b) { vi s = a; for (ui i = 0; i < b.size(); i++) s.pb(b[i]); sort(s.begin(), s.end()); int k = unique(s.begin(), s.end()) - s.begin(), x, y; if (n == k) { int c[m]; memset(c, 0, sizeof(c)); for (ui i = 0; i < a.size(); i++) if (a[i] < m) ++c[a[i]]; for (ui i = 0; i < b.size(); i++) if (b[i] < m) ++c[b[i]]; for (int i = m - 1; ~i; i--) if (c[i] == 1) return i; return -1; } vector< pair< int, ll > > e[2*k+1]; for (int i = 0; i < k; i++) e[2*k].pb(mp(i, s[i])), e[i+k].pb(mp(i, m)); exgcd(m, n, x, y), x = (x % n + n) % n; pi p[k]; for (int i = 0; i < k; i++) p[i] = mp(1ll * x * (s[i] - s[0]) % n, i); sort(p, p + k); for (int i = 0, j = 1 % k; i < k; i++, j = (++j == k) ? 0 : j) e[p[i].se].pb(mp(p[j].se + k, 1ll * m * (p[j].fi - p[i].fi - 1 < 0 ? p[j].fi - p[i].fi - 1 + n : p[j].fi - p[i].fi - 1))); map< int, int > h; for (int i = 0; i < k; i++) h[s[i]] = i; for (int i = 0; i < k; i++) if (h.find((s[i] + m) % n) != h.end()) { int j = h[(s[i]+m)%n]; e[i].pb(mp(j + k, 0)), e[j+k].pb(mp(i, 0)); } pq< pair< ll, int > > q; int v[2*k+1]; ll d[2*k+1], now = 0; memset(v, 0, sizeof(v)); memset(d, 0x3f, sizeof(d)); q.push(mp(0, 2 * k)), d[2*k] = 0; while (q.size()) { int x = q.top().se; q.pop(); if (v[x]) continue; v[x] = 1, now = max(now, d[x]); for (ui i = 0; i < e[x].size(); i++) { int y = e[x][i].fi; ll z = e[x][i].se; if (d[y] > d[x] + z) d[y] = d[x] + z, q.push(mp(-d[y], y)); } } return now; } int main() { rd(n), rd(m), rd(B); for (int i = 1; i <= B; i++) rd(b[i]); rd(G); for (int i = 1; i <= G; i++) rd(g[i]); if (n < m) swap(n, m), swap(B, G), swap(b, g); if ((d = gcd(n, m)) > B + G) Fail; n /= d, m /= d; for (int i = 1; i <= B; i++) a[b[i]%d].pb(b[i] / d); for (int i = 1; i <= G; i++) f[g[i]%d].pb(g[i] / d); for (int i = 0; i < d; i++) if (!a[i].size() && !f[i].size()) Fail; for (int i = 0; i < d; i++) ans = max(ans, solve(a[i], f[i]) * d + i); print(ans); return 0; } ```