题意

题目链接

给定一个长度为 $n$ 的 $A$ 数组和 $B$ 数组，你有两个集合 $S_1,S_2$ 初始时为空。每次你的操作是选择两对 $(i,j),(p,q)$ 满足 $(i,j) \notin S_1,(p,q) \notin S_2,A_i<B_j,B_p<A_q,\gcd(A_i,B_j) \neq 1,\gcd(A_q,B_p) \neq 1,\gcd(A_q,B_p,A_i,B_j) \neq 1$ 然后将 $(i,j)$ 加入 $S_1$ ，将 $(p,q)$ 加入 $S_2$。

要求你制定一种策略 使得最终的 $|S_1|$ 尽量大。

$n \leq 400,1 \leq \text{all input} \leq 10^9$

题解

发现只有最后那个很长的 gcd 限制是和两个有关的 其他的限制都只和自己有关。这让我们想到了二分图最大匹配。

考虑一个很暴力的做法：枚举所有的二元组都建个点 满足 $\gcd$ 不为 $1$ 的两点之间连边 跑二分图最大匹配即可。这个图点数和边数都上天显然过不去。

我们考虑先将这个图转成网络流 思考一下如何优化点和边

• 优化 1：两个 gcd 相同的二元组连出的边一定都是一样的 于是可以将这些二元组合并
• 优化 2：我们可以建立虚点来优化连边 我们可以枚举一个质数 $p$ 然后用这个质数处理所有 $p | \gcd$ 的对（也就是所有是 $p$ 的倍数的向它连边）

这样再跑网络流复杂度就很正确了。

const int MAXN = 1e6 + 5;
namespace Flow{
    struct Edge{
        int to,w,nxt;
    }e[MAXN<<1];
    int head[MAXN],cur[MAXN],cnt=1;
    int dep[MAXN];
    int S,T,N;
    
    inline void clear(){
        FOR(i,0,N) head[i] = 0;cnt = 1;
    }

    inline void add(int u,int v,int w){
        e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
        e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
    }

    inline bool bfs(){
        FOR(i,0,N) cur[i] = head[i],dep[i] = 0;
        std::queue<int> q;q.push(S);dep[S] = 1;
        while(!q.empty()){
            int v = q.front();q.pop();
            for(int i = head[v];i;i = e[i].nxt){
                if(e[i].w > 0 && !dep[e[i].to]){
                    dep[e[i].to] = dep[v] + 1;
                    if(e[i].to == T) return true;
                    q.push(e[i].to);
                }
            }
        }
        return dep[T];
    }

    inline int dfs(int v,int flow=1e9){
        if(v == T) return flow;
        if(!flow) return 0;
        int ans = 0;
        for(int &i = cur[v];i;i = e[i].nxt){
            if(e[i].w > 0 && dep[e[i].to] == dep[v] + 1){
                int t = dfs(e[i].to,std::min(flow,e[i].w));
                if(t>0){
                    ans += t;flow -= t;
                    e[i].w -= t;e[i^1].w += t;
                    if(!flow) break;
                }
        }
        }
        return ans;
    }

    inline int Dinic(){
        int ans = 0,t = 0;
        while(bfs()) while((t=dfs(S))) ans += t;
        return ans;
    }
};
using namespace Flow;

int n,a[MAXN],b[MAXN];
std::map<int,int> L,R,D;
std::set<int> G;
int t[MAXN],tot;

inline void Solve(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",a+i);
    FOR(i,1,n) scanf("%d",b+i);
    L.clear();R.clear();D.clear();G.clear();tot = 0;
    FOR(i,1,n){
        FOR(j,1,n){
            int g = std::__gcd(b[j],a[i]);
            if(g == 1) continue;
            if(b[j] > a[i]){
                if(!L[g]) L[g] = ++tot,t[tot] = 0,G.insert(g);
                t[L[g]]++;
            }
            if(b[j] < a[i]){
                if(!R[g]) R[g] = ++tot,t[tot] = 0,G.insert(g);
                t[R[g]]++;
            }
        }
    }
    for(auto x:G){
        int q = std::sqrt(1.0*x);int tmp = x;
        FOR(i,2,q){
            if(!(tmp%i)){
                if(!D[i]) D[i] = ++tot;
                while(!(tmp%i)) tmp /= i;
            }
        }
        if(tmp != 1) if(!D[tmp]) D[tmp] = ++tot;
    }
    clear();N = tot;S = ++N;T = ++N;
    for(auto x:L){
        add(S,x.se,t[x.se]);
        int q = std::sqrt(1.0*x.fi),tmp = x.fi;
        FOR(i,2,q){
            if(!(tmp%i)){
                if(D[i]) add(x.se,D[i],1e9);
                while(!(tmp%i)) tmp /= i;
            }
        }
        if(tmp != 1) if(D[tmp]) add(x.se,D[tmp],1e9);
    }
    for(auto x:R){
        add(x.se,T,t[x.se]);
        int q = std::sqrt(1.0*x.fi),tmp = x.fi;
        FOR(i,2,q){
            if(!(tmp%i)){
                if(D[i]) add(D[i],x.se,1e9);
                while(!(tmp%i)) tmp /= i;
            }
        }
        if(tmp != 1) if(D[tmp]) add(D[tmp],x.se,1e9);
    }
    printf("%d\n",Dinic());
}

int main(){
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

有趣的事情

这题理论来说答案是可以爆 int 的，但是没开 long long 也过了。。可能不好卡。