题目传送门

题目分析

70pts

全网都搜不到题解，连题面都搜不到，真是一件悲伤的事。
正解是网络流，但模型建的不对可能会导致TLE，虽然数据规模看起来是能过的。
首先我们来想一种比较简单的建模方式，将两边$GCD>1$的点连一条容量为1的弧,然后去跑Dinic，亲测70分。

代码

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
92
93
94
95
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# define R register
# define LL long long
# define inf 2000101900

using namespace std;

queue <int> q;
int n,m,s,t,e,a[510],b[510],h[1010],v[1010],ans,T,used[1010];
struct zx{int v,flow,pre;} ed[2000010];

template <typename T> void in(R T& a){
    R T x=0,f=1; R char c = getchar();
    while(!isdigit(c)){if(c == '-') f=-1; c = getchar();}
    while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
    a = x*f;
}

inline int gcd(R int x,R int y){return y==0? x:gcd(y,x%y);}

inline void add(R int x,R int y,R int z){
    ed[++e] = (zx){y,z,h[x]};
    h[x] = e;
}

inline bool bfs(){
    memset(v,0,sizeof(v));
    q.push(s);
    v[s] = 1;
    while(!q.empty()){
        R int x = q.front();
        q.pop();
        for(R int i=h[x]; i!=-1; i=ed[i].pre)
        {
            R int p = ed[i].v;
            if(v[p] || !ed[i].flow) continue;
            v[p] = v[x]+1;
            q.push(p);
        }
    }
    return v[t];
}

inline int maxflow(R int x,R int want){
    if(!want || x == t) return want;
    R int flow = 0;
    for(R int i=used[x]; i!=-1; i=ed[i].pre)
    {
        R int p = ed[i].v;
        if(v[p] != v[x]+1|| !ed[i].flow) continue;
        R int f = maxflow(p,min(ed[i].flow,want));
        if(!f) continue;
        want -= f;
        flow += f;
        ed[i].flow -= f;
        ed[i^1].flow += f;
    }
    return flow;
}

int main(){
    in(T);
    while(T--){
        memset(h,-1,sizeof(h));
        e=-1,ans=0;
        in(m),in(n);
        s=0,t=m+n+1;
        for(R int i=1; i<=m; ++i) in(a[i]);
        for(R int i=1; i<=n; ++i) in(b[i]);
        for(R int i=1; i<=m; ++i)
        {
            add(s,i,1);
            add(i,s,0);
        }
        for(R int i=1; i<=n; ++i)
        {
            add(i+m,t,1);
            add(t,i+m,0);
        }
        for(R int i=1; i<=m; ++i)
            for(R int j=1; j<=n; ++j)
                if(gcd(a[i],b[j]) != 1) add(i,j+m,1),add(j+m,i,0);
        while(bfs()){
            memcpy(used,h,sizeof(h));
            ans += maxflow(s,inf);
        }
        printf("%d\n",ans);
    }
    return 0;
}

AC

以上就是比较简单的网络流，用二分图也能解出来，但是$n^{2}$去建边是导致TLE的直接原因，因此我们就要考虑更换一种建模方式。
我们再来考虑，对于两个数字，如果他们的$GCD>1$，就意味着他们有至少一个共同的质因子，因此我们可以想，能否借助这个性质来建模呢?
我们可以先将每一个数都质因数分解，然后将所有出现过的质因数都放在一个集合里紧接着，对于每一个数字，我们将它与所有的因子各建一条容量为1的弧(当然，数字颜色不同时弧的方向也是不同的)，然后超级源连向一种颜色，超级汇连向另外一种颜色，按照这样的模型再去跑Dinic，就可以通过了。

代码

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <queue>
# include <cmath>
# define R register
# define LL long long
# define inf 2000101900

using namespace std;

queue <int> q;
int n,m,s,t,e,h[10010],v[10010],ans,T,used[10010];
int pri[664580],p,phi[1010][1010],pos[664580],cnt,num;
struct zx{int v,flow,pre;} ed[2000010];
bool vis[10000010];

template <typename T> void in(R T& a){
    R T x=0,f=1; R char c = getchar();
    while(!isdigit(c)){if(c == '-') f=-1; c = getchar();}
    while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
    a = x*f;
}

inline void add(R int x,R int y,R int z){
    ed[++e] = (zx){y,z,h[x]};
    h[x] = e;
}

inline bool bfs(){
    memset(v,0,sizeof(v));
    q.push(s);
    v[s] = 1;
    while(!q.empty()){
        R int x = q.front();
        q.pop();
        for(R int i=h[x]; i!=-1; i=ed[i].pre)
        {
            R int p = ed[i].v;
            if(v[p] || !ed[i].flow) continue;
            v[p] = v[x]+1;
            q.push(p);
        }
    }
    return v[t];
}

inline int maxflow(R int x,R int want){
    if(!want || x == t) return want;
    R int flow = 0;
    for(R int i=used[x]; i!=-1; i=ed[i].pre)
    {
        R int p = ed[i].v;
        if(v[p] != v[x]+1|| !ed[i].flow) continue;
        R int f = maxflow(p,min(ed[i].flow,want));
        if(!f) continue;
        want -= f;
        flow += f;
        ed[i].flow -= f;
        ed[i^1].flow += f;
    }
    return flow;
}

int main(){
	for(R int i=2; i<=10000000; ++i)
	{
		if(!vis[i]) pri[++p] = i;
		for(R int j=1; j<=p&&i*pri[j]<=10000000; ++j)
		{
			vis[i*pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
	in(T);
    while(T--){
        memset(h,-1,sizeof(h));
        e=-1,ans=0;
        in(m),in(n);
		cnt = 0;
		memset(phi,0,sizeof(phi));
		for(R int i=1; i<=m+n; ++i)
		{
			in(num);
			for(R int j=1; j<=p&&num>=pri[j]; ++j)
			{
				if(num%pri[j] == 0) pos[++cnt] = pri[j],phi[i][++phi[i][0]] = pri[j];
				while(num%pri[j] == 0) num /= pri[j];
			}
		}

		sort(pos+1,pos+cnt+1);
		cnt = unique(pos+1,pos+cnt+1)-pos-1;
		s=0,t=m+n+cnt+1;

        for(R int i=1; i<=m; ++i)
        {
            add(s,i,1);
            add(i,s,0);
        }
        for(R int i=m+1; i<=m+n; ++i)
        {
            add(i,t,1);
            add(t,i,0);
        }
        for(R int i=1; i<=m; ++i)
		{
			for(R int j=1; j<=phi[i][0]; ++j)
			{
				R int cs = lower_bound(pos+1,pos+cnt+1,phi[i][j])-pos+n+m;
				add(i,cs,1);
				add(cs,i,0);
			}
		}

		for(R int i=m+1; i<=m+n; ++i)
		{
			for(R int j=1; j<=phi[i][0]; ++j)
			{
				R int cs = lower_bound(pos+1,pos+cnt+1,phi[i][j])-pos+n+m;
				add(cs,i,1);
				add(i,cs,0);
			}
		}
        while(bfs()){
            memcpy(used,h,sizeof(h));
            ans += maxflow(s,inf);
        }
        printf("%d\n",ans);
    }
    return 0;
}