CF516E Drazil and His Happy Friends 题解
Visits: 304
题意
- 有 $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$。
我们要连三类边：
- $S \stackrel{i}{\longrightarrow} A_i$
- $B_i \stackrel{m}{\longrightarrow} A_i$
- $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)$。
代码
#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;
}
