「Codeforces 498C」Array and Operations

发表于 | | 阅读次数:
字数统计: 1.1k 字

Description

题目链接：Codeforces 498C

你有一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$ 和 $m$ 对整数 $(i_1,j_1),(i_2,j_2),\dots,(i_m,j_m)$。每一对整数 $(i_k,j_k)$ 都满足 $i_k+j_k$ 的值是奇数，且 $1\le i_k<j_k\le n$。

每一次操作你可以进行一系列行为：

  1. 在 $m$ 个数对中选择一个 $(i_k,j_k)$ 和一个整数 $v$ 满足 $v>1$，并且 $v$ 整除 $a_{i_k}$ 和 $a_{j_k}$。
  2. 将 $a_{i_k}$ 和 $a_{j_k}$ 都除以 $v$。

请计算出能够进行的最大操作次数。注意，每一对数可能多次使用。

数据范围：$2\le n\le 100$，$1\le m\le 100$，$1\le a_i\le 10^9$

Solution

首先注意到一个重要的性质：$i_k+j_k$ 为奇数。换言之，我们可以把原序列按照下标奇偶性分成两部分，下标为 $i_k$ 和 $j_k$ 的两个数一定不是同一个部分的。也就是说，如果我们在 $i_k$ 和 $j_k$ 之间连边，那么这是一张二分图。

我们建立出这张二分图，新建一个源点和汇点，每个点向源点或汇点连一条容量为 $\vert S_{a_i}\vert$ 的边（其中 $S_{i}$ 为 $i$ 的质因子可重集合，如 $12$ 的质因子集合为 $\{2,2,3\}$ ），$a_{i_k}$ 和 $a_{j_k}$ 之间的边的容量为 $\vert S_{a_{i_k}}\cap S_{a_{j_k}}\vert$（质因子集合交集大小）。

看起来直接跑最大流就行了？其实很容易找到反例。因为同一个数的质因子不是独立的，一旦被除去之后就不能被别的数字配对。那么我们可以想到拆点。

  • 对于数字 $x$，我们把他拆成质因子个数个点，每个质因子向源点或汇点连一条容量为其指数的边。
  • 对于两个数字 $x,y$，我们定义代表的质因子相同的点性质相同。我们把 $x,y$ 性质相同的点连边，容量为这个质因子在 $x$ 和 $y$ 中指数的较小值。
  • 直接跑最大流即可。

时间复杂度：$O(m\sqrt n)$，前面应该有一个较大常数，因为点最多有 $9n$ 个，边最多有 $9m$ 条。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
typedef std::pair<int,int> pii;
typedef std::pair<pii,int> ppi;

const int N=2e3+5,M=2e5+5;
int n,m,idx,tot=1,lnk[N],cnr[N],ter[M],nxt[M],val[M],dep[N];
std::vector<ppi> a[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
    add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
    memset(dep,0,sizeof(dep));
    memcpy(cnr,lnk,sizeof(lnk));
    std::queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
        }
    }
    return dep[t];
}
int dfs(int u,int t,int flow) {
    if(u==t) return flow;
    int ans=0;
    for(int &i=cnr[u];i&&ans<flow;i=nxt[i]) {
        int v=ter[i];
        if(val[i]&&dep[v]==dep[u]+1) {
            int x=dfs(v,t,std::min(val[i],flow-ans));
            if(x) val[i]-=x,val[i^1]+=x,ans+=x;
        }
    }
    if(ans<flow) dep[u]=-1;
    return ans;
}
int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t)) {
        int x;
        while((x=dfs(s,t,1<<30))) ans+=x;
    }
    return ans;
}
std::vector<ppi> solve(int x) {
    std::vector<ppi> ans;
    for(int i=2;i*i<=x;++i) {
        if(x%i) continue;
        int cnt=0;
        while(x%i==0) x/=i,++cnt;
        ans.push_back(ppi(pii(i,cnt),++idx));
    }
    if(x>1) ans.push_back(ppi(pii(x,1),++idx));
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) {
        int x;
        scanf("%d",&x);
        a[i]=solve(x);
    }
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        if(v&1) std::swap(u,v);
        for(ppi x:a[u]) for(ppi y:a[v]) {
            if(x.first.first==y.first.first) {
                addedge(x.second,y.second,std::min(x.first.second,y.first.second));
            }
        }
    }
    int s=0,t=idx+1;
    for(int i=1;i<=n;i+=2) {
        for(ppi x:a[i]) addedge(s,x.second,x.first.second);
    }
    for(int i=2;i<=n;i+=2) {
        for(ppi x:a[i]) addedge(x.second,t,x.first.second);
    }
    int ans=dinic(s,t);
    printf("%d\n",ans);
    return 0;
}
0%