CF516E Drazil and His Happy Friends

Description

有 \(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\)。

Link

Solution

首先对于男生 \(x\) 和女生 \(y\) 判断他们能一起玩的条件是什么。

设他们在第 \(i\) 天玩，那么有 \(i \bmod n=x,i \bmod m=y\)。

用 \(x,y\) 表示 \(i\)，\(i=x+kn=y+pm\)。整理一下，得 \(kn-pm=y-x\)。

方程有解的充要条件是 \(\gcd(n,m) \mid y-x\)，也就是 \(x,y\) 在模 \(\gcd(n,m)\) 意义下同余。

设 \(d=\gcd(n,m)\) ，那么我们可以以模 \(d\) 的结果为依据，将男生和女生分为 \(d\) 组。

在每一组内，只要有一个初始快乐的人，整个组都会变快乐。我们有了无解的条件：

1. \(d>B+G\)；
2. 存在某一组没有初始快乐的人。

两个条件满足其一即无解。如果有解，\(d\) 必定小于等于 \(2 \times 10^5\)。

接下来我们对每一组分别求解，取 \(\max\) 就是最终答案。

考虑对某一组求解。

设 \(n’=n/d,m'=m/d\)，此时有 \(\gcd(n',m')=1\)。一组内，不同的男生与女生分别有 \(n'\) 个和 \(m'\) 个。

为了方便，如果 \(n'<m'\)，我们就交换男女生的所有信息。现在 \(n' \geq m'\)。

对于一个男生 \(x\)，如果他在第 \(i\) 天被女生 \(i \bmod m\) 变快乐，那么在第 \(i+m\) 天男生 \((x+m)\bmod n\) 也会快乐。

同理，女生 \(y\) 在第 \(i\) 天变快乐，那么在 \(i+n\) 天女生 \((y+n)\bmod m\) 也会快乐。

由于 \(\gcd(n',m')=1\)，在 \(n'm'\) 的周期内，每对男女生都会不重不漏地一起玩。

由此，我们有引理：

Lemma：在某一组内，如果某一天所有男生都快乐了，那么除非当前天数小于 \(m\)，所有女生也必定快乐。

Proof：对于最后的 \(m\) 天，每个女生都恰好出来玩了一次。

在最后 \(m\) 天内的某一天 \(i\)，由于男生在最后全部快乐，那么这一天对应的男女生不可能都不快乐。要么初始都快乐，要么一个影响另一个。于是女生也必定全部快乐。

那么接下来只需要考虑男生即可。

对于某一组，如果女生 \(g_i\) 初始快乐，那么也把男生 \(g_i\) 标记为初始快乐，相当于把初始快乐的男女生合并。

首先判掉所有男生都被标记为初始快乐的情况。按照上面的分析，我们可以建图跑同余最短路：

1. \(S \xrightarrow{i} i\)；
2. \(i \xrightarrow{m} (i+m)\bmod n\)。

其中 \(S\) 是超级源点。但此时点数是 \(10^9\) 级别的，无法接受。

考虑删掉一些没用的点。如果 \(i\) 与 \((i+m)\bmod n\) 初始都不快乐，那么 \(i\) 必定先快乐，则 \(i\) 一定不会成为答案。

那么我们只有两类有用的点：\(A\) 类点是初始快乐的点，\(B\) 类点是 \((i+m)\bmod n\) 初始快乐的点。

我们以某一个 \(A\) 为起点，在长度为 \(n\) 的环上，以 \(m\) 为步长，Exgcd 求出起点走到每一个 \(A_i\) 的步数。

以步数为关键字对 \(A\) 重新排序并标号。\(v(x)\) 为 \(x\) 号节点在环上的位置，\(k\) 为初始快乐个数，我们可以重新建边：

1. \(S \xrightarrow{v(A_i)} A_i\)；
2. \(B_i \xrightarrow{m} A_i\)；
3. \(A_i \xrightarrow{xm} B_{(i+1)\bmod k}\)

其中 \(x\) 是使得 \(xm \equiv B_j-A_i \pmod{n}\) 最小非负整数 \(x\)。Exgcd 求解即可。

注意到具体实现过程中只需要一次 Exgcd 求出 \(xm\equiv \gcd(n,m) \pmod{n}\) 最小的非负整数解。其他方程的右边必定是 \(\gcd(n,m)\) 的倍数，对应的 \(x\) 乘上若干倍再取余即可。

一定程度上参考了 xht 的题解。

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define Ckmax(x,y) x=max(x,y)
#define Ckmin(x,y) x=min(x,y)
#define ull unsigned long long
using namespace std;
const int N=4e5+5;
const int IINF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}

template<typename Type>
inline void read(Type &res){
    Type x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    res=x*f;
}

ll n,m,b[N],g[N],d;
int B,G;
vector<ll> sb[N],sg[N];

int head[N],tot;
bool vis[N];
ll dis[N];

struct Edge{
    int to,nxt;
    ll val;
}edge[N<<2];

void Add(int u,int v,ll w){
    edge[++tot]={v,head[u],w};
    head[u]=tot;
}

void Exgcd(ll va,ll vb,ll &x,ll &y){
    if(!vb) return x=1,y=0,void();
    Exgcd(vb,va%vb,x,y);
    ll z=x; x=y; y=z-va/vb*y;
}

ll Solve(vector<ll> tb,vector<ll> tg){
    vector<ll> s;
    vector<pll> p;
    for(ll i:tb) s.push_back(i);
    for(ll i:tg) s.push_back(i);
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    int k=s.size(); p.resize(k);
    if(k==n/d){
        map<ll,int> cnt;
        for(ll i:tb) if(i<m) cnt[i]++;
        for(ll i:tg) if(i<m) cnt[i]++;
        ll ans=-1;
        for(auto i:cnt){
            if(i.second==1)
                Ckmax(ans,i.first);
        }
        return ans;
    }
    ll len,tmp; Exgcd(n,m,tmp,len);
    len=((len%(n/d))+(n/d))%(n/d);
    int S=(k<<1);
    for(int i=0;i<k;i++) p[i]=make_pair((s[i]-s[0])/d*len%(n/d),i);
    sort(p.begin(),p.end());
    for(int i=0;i<=(k<<1);i++) head[i]=0;
    tot=0;
    for(int i=0;i<k;i++){
        Add(S,i,s[i]);
        Add(i+k,i,m);
    }
    if(k==1) Add(0,k,(n-m)/d*len%(n/d)*m);
    else{
        for(int i=0,j=1;i<k;i++,j=(j+1)%k){
            ll w=((s[p[j].second]-m+n)%n-s[p[i].second]+n)%n/d*len%(n/d)*m;
            Add(p[i].second,p[j].second+k,w);
        }
    }
    for(int i=0;i<=(k<<1);i++){
        dis[i]=LINF;
        vis[i]=0;
    }
    priority_queue<pli,vector<pli>,greater<pli> > q;
    q.push({0,k<<1});
    dis[k<<1]=0;
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].nxt){
            int t=edge[i].to;
            if(vis[t]) continue;
            if(dis[t]>dis[x]+edge[i].val){
                dis[t]=dis[x]+edge[i].val;
                q.push({dis[t],t});
            }
        }
    }
    ll res=0;
    for(int i=0;i<=(k<<1);i++) Ckmax(res,dis[i]);
    // printf("Res=%lld\n",res);
    return res;
}

signed main(){
    //效率！效率！
    FileIO();
    read(n),read(m);
    read(B);
    for(int i=0;i<B;i++) read(b[i]);
    read(G);
    for(int i=0;i<G;i++) read(g[i]);
    if(n<m) swap(n,m),swap(B,G),swap(b,g);
    d=__gcd(n,m);
    if(d>B+G) return puts("-1"),0;
    for(int i=0;i<B;i++) sb[b[i]%d].push_back(b[i]);
    for(int i=0;i<G;i++) sg[g[i]%d].push_back(g[i]);
    for(int i=0;i<d;i++){
        if(sb[i].empty()&&sg[i].empty()){
            puts("-1");
            return 0;
        }
    }
    ll ans=0;
    for(int i=0;i<d;i++)
        Ckmax(ans,Solve(sb[i],sg[i]));
    printf("%lld\n",ans);
    return 0;
}