洛谷P2065 [TJOI2011] 卡片 题解
题目链接：P2065 [TJOI2011] 卡片
题意：
桌子上现在有 \(n\) 张蓝色卡片和 \(m\) 张红色卡片，每张卡片上有一个大于 \(1\) 的整数 \(x\) 。
现在你要从桌子上拿走一些卡片，分若干次拿。
每次只能拿走一组卡片：这组卡片颜色不同，并且两张卡片上面的数字的最大公约数大于 \(1\)。
问最多可以从桌上拿走多少组卡片。
输入格式：
文件的第一行读入一个整数 \(T\) ，为数据组数。
对于每组数据，第一行给出 \(n,m\) 。
第二行给出每张蓝色卡片上面的数字，第三行给出每张红色卡片上的数字。
输出格式：
对每组测试数据，输出最多可以拿走多少组卡片。
数据范围：
\(1\le T\le 100,~1\le m,n\le 500\) ，卡片上的数字 \(x\) 满足 \(1 \le x \le 10^7\) 。
虽说网络流复杂度很宽松，但是直接 \(\mathcal{O}(n^2)\) 暴力建边是不行滴。
考虑对卡片上的每个数质因数分解，称这些质因数的并为点集 \(P\) 。
称 \(A\) 为蓝色卡片的点集，称 \(B\) 为红色卡片的点集。
- 每张蓝色卡片向其所含的素因子连边，流量为 \(1\) 。
- 每张红色卡片所含的素因子向这张卡片连边，流量为 \(1\) 。
- 源点 \(s\) 向 \(A\) 连边，流量为 \(1\) 。\(B\) 向汇点 \(t\) 连边，流量为 \(1\) 。
跑一遍最大流就是答案了。然后分析一波复杂度。
点数 \(\mathcal{O}(2n + \overline{\omega} n) = \mathcal{O}(c_1n)\) ，边数 \(\mathcal{O}(4\overline{\omega}n + 4n) = \mathcal{O}(c_2n)\)
其中 \(\overline\omega\) 表示每个数贡献的质因子个数的一个期望值。
这个 \(\overline\omega\) 的范围需要分析一下。注意到当一个数贡献了 \(k\) 个质因子时，至少有一个质因子小于 \(\sqrt[k]{M}\) 。
当贡献 \(2\) 个因子时，尽管此时有很多质因子，但这样的总贡献不会大于 \(2n\) 。
当贡献 \(3\) 个因子时，至少有一个质因子小于 \((\sqrt[3]{M} \approx 216)\)，而 \(n\le 500\) ，可以发现至多贡献 \(648\) 。
当贡献 \(4\) 个因子时，至多贡献 \(224\) 个质因子。归纳法可知越往后贡献越小，还不如贡献 \(2\) 个因子的时候。
因此事实上 \(\overline\omega \le 2\) ，在数据随机的时候甚至可以小于 \(1\) ，因此我们可以得到 \(c_1 \le 4,c_2 \le 12\) 。
理论时间复杂度上界为 \(\mathcal{O}\left(Tc_1^2c_2n^3+T\frac{2\sqrt{M}}{\ln M}\right)\) ，把 \(n=500\) 代入可以发现数量级大约 \(2\times 10^{12}\) 。
然而这题的数据还是很随机的，并且这个上界很难达到，所以能过。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
// N = 2015, M = 8060
#define N ((int)(2 * 500 + 2 * 500 + 15))
#define M ((int)((2 * 500 * 2 + N + 15) * 2))
#define K ((int)(3355))
unordered_map<int,int> vis;
// A: 1 ~ n, B: n+1 ~ n+m, P: n+m+1 ~ n+m+k
int n,m,k,s,t,tot,cnt,pos=1,pri[K],p[K],head[N],now[N],dep[N];
struct Edge { int u,v,w,next; } e[M];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
void add(int u,int v,int w) { addEdge(u,v,w); addEdge(v,u,0); }
queue<int> q; bitset<K> ck;
void init_prime()
{
for(int i=2; i<=K-5; i++)
{
if(!ck[i]) pri[++cnt] = i;
for(int j=1; j<=cnt && i * pri[j] <= K-5; j++)
{ ck[i * pri[j]] = 1; if(i % pri[j] == 0) break;}
}
}
bool bfs()
{
for(int i=1; i<=tot; i++) dep[i] = INF;
dep[s] = 1; q.push(s); now[s] = head[s];
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].v;
if(e[i].w > 0 && dep[v] == INF)
{
dep[v] = dep[u] + 1;
now[v] = head[v]; q.push(v);
}
}
}
return dep[t] != INF;
}
int dfs(int u,int in)
{
if(u == t) return in;
int out = 0;
for(int i=now[u]; i && in; i = e[i].next)
{
int v = e[i].v; now[u] = i;
if(e[i].w > 0 && dep[v] == dep[u] + 1)
{
int res = dfs(v, min(in, e[i].w));
e[i].w -= res; e[i ^ 1].w += res;
in -= res; out += res;
}
}
if(!out) dep[u] = INF;
return out;
}
int Dinic()
{
int res = 0;
while(bfs()) res += dfs(s,INF);
return res;
}
void proc1(int x,int id)
{
int o = 0;
for(int i=1; i<=cnt && pri[i] * pri[i] <= x; i++)
if(x % pri[i] == 0)
{ p[++o] = pri[i]; while(x % pri[i] == 0) x /= pri[i]; }
if(x > 1) p[++o] = x;
for(int i=1; i<=o; i++)
{
if(!vis[p[i]]) vis[p[i]] = ++k;
add(id, n + m + vis[p[i]], 1);
}
}
void proc2(int x,int id)
{
int o = 0;
for(int i=1; i<=cnt && pri[i] * pri[i] <= x; i++)
if(x % pri[i] == 0)
{ p[++o] = pri[i]; while(x % pri[i] == 0) x /= pri[i]; }
if(x > 1) p[++o] = x;
for(int i=1; i<=o; i++)
if(vis[p[i]]) add(n + m + vis[p[i]], id, 1);
}
void clear()
{
pos = 1; k = 0; vis.clear();
for(int i=1; i<=tot; i++) head[i] = 0;
}
void solve()
{
clear(); cin >> n >> m;
for(int i=1,x; i<=n; i++) { cin >> x; proc1(x, i); }
for(int i=1,x; i<=m; i++) { cin >> x; proc2(x, n + i); }
s = n + m + k + 1; tot = t = s + 1;
for(int i=1; i<=n; i++) add(s, i, 1);
for(int i=1; i<=m; i++) add(n + i, t, 1);
cout << Dinic() << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
init_prime();
int _Q; cin >> _Q; while(_Q--) solve();
return 0;
}
