纪念一下独立切的 *3100 的数论 + 贪心题，思考时的思路一波三折，像极了考试中的我。
个人感觉难度至少 *3300。
考虑先求出 \(d = \gcd(n, m)\)，那么编号根据模 \(d\) 结果分成了 \(0...d-1\) 共 \(d\) 个部分，每个部分里的人不能和外面的人玩。
因此当 \(d> b + g\) 时一定无解，接下来我们对 \(d\) 个部分分开处理。
我们考虑求出使得全部女生快乐的最小天数，求男生的天数只需要把两堆人对调。
考虑编号为 \(0\) 的男生，第一次和编号为 \(0\) 的女生玩，第二次和编号为 \(n\bmod m\) 的女生玩，第三次和编号为 \(2n\bmod m\) 的女生玩，以此类推。
那么我们把 \(0...m-1\) 建一个环，对于环上的一个点 \(u\)，向 \((u+n) \bmod m\) 连边。
钦定环上一个点的 id 为从 \(0\) 开始走的步数，我们容易使用 exgcd 算出一个点的 id。
把所有快乐的女生编号对应的 id，以及快乐的男生编号 \(\bmod m\) 对应的 id 拎出来，排个序。
对于每个拎出来的点 \(u\)，算出环上 id 为 \(u-1\) 的女生的答案，容易通过拎出来的前一个点算出，可以发现这考虑了所有女生的答案。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define fi first
#define se second
#define pir pair <ll, ll>
#define mkp make_pair
#define pb push_back
using namespace std;
void read(ll &x) {
char c; ll f = 1;
while(!isdigit(c = getchar()))
if(c == '-') f = -1;
x = c - '0';
while(isdigit(c = getchar())) x = x * 10 + c - '0';
x *= f;
}
const ll maxn = 4e5 + 10, inf = 1e17;
ll nl, ml, n, m, g;
vector <ll> v1[maxn], v2[maxn];
ll ans;
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1, y = 0;
return;
}
exgcd(b, a%b, x, y);
ll t = x;
x = y, y = t - a / b * y;
}
ll Get(ll i) {
ll x, y;
exgcd(nl, ml, x, y);
x *= i, y *= i;
x = (x % ml + ml) % ml;
return x;
}
ll iGet(ll i) {return i * nl % ml;}
ll h[maxn], ht, mn[maxn], vis[maxn];
void solve(ll u) {
ht = 0;
for(ll i: v1[u]) {
ll x = i / g;
ll id = Get(x % ml);
h[++ht] = id;
}
for(ll i: v2[u]) {
ll x = i / g;
ll id = Get(x);
h[++ht] = id;
}
if(!ht) {ans = inf; return;}
sort(h + 1, h + 1 + ht);
ht = unique(h + 1, h + 1 + ht) - h - 1;
for(ll i = 1; i <= ht; i++)
mn[i] = inf, vis[i] = 0;
for(ll i : v1[u]) {
ll x = i / g;
ll id = Get(x % ml);
ll Id = lower_bound(h + 1, h + 1 + ht, id) - h;
mn[Id] = min(mn[Id], i);
}
for(ll i : v2[u]) {
ll x = i / g;
ll id = Get(x);
ll Id = lower_bound(h + 1, h + 1 + ht, id) - h;
mn[Id] = min(mn[Id], i), vis[Id] = 1;
}
for(ll i = 1; i <= ht; i++) {
ll x = (h[i] + ml - 1) % ml, j = (i + ht - 2) % ht + 1;
if(x == h[j] && vis[j]) continue;
ll ret = mn[j] + (x - h[j] + ml) % ml * nl * g;
ans = max(ans, ret);
}
}
int main() {
read(nl), read(ml), read(n);
g = __gcd(nl, ml);
nl /= g, ml /= g;
if(g > 2e5) {puts("-1"); return 0;}
for(ll i = 1, x; i <= n; i++) {
read(x);
v1[x % g].pb(x);
}
read(m);
for(ll i = 1, x; i <= m; i++) {
read(x);
v2[x % g].pb(x);
}
for(ll i = 0; i < g; i++) {
sort(v1[i].begin(), v1[i].end());
sort(v2[i].begin(), v2[i].end());
}
for(ll i = 0; i < g; i++)
solve(i);
for(ll i = 0; i < g; i++) swap(v1[i], v2[i]);
swap(nl, ml);
for(ll i = 0; i < g; i++)
solve(i);
if(ans == inf) ans = -1;
printf("%lld", ans);
return 0;
}