Description：

$n$ 种数字，第 $i$ 种数字是 $a_i$ 、有 $b_i$ 个，权值是 $c_i$ 。若两个数字满足 $a_i$ 是 $a_j$ 的倍数，且 $a_i/a_j$ 是一个质数，这两个数字可以配对，并获得 $c_i \times c_j$ 的价值。获得的价值总和不小于 $0$ 的前提下，求最多进行多少次配对。

$1\leqslant n\leqslant 200$

Solution：

可以发现如果两个数可以配对那么他们可以分解成的素因子个数相差一，那么我们可以利用这个先把每个数的唯一分解求出来然后就可以判断能否匹配了，但是这样还是没法建图，然而发现这个其实是一个二分图，因为每个数只会朝分解素因子个数和他相差 $1$ 的连边，于是用最小费用最大流一直增广到和为负即可，注意最后一个可能没拿满要特判。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 210

typedef long long ll;

struct num

{

	int k,c;

	ll v;

	bool operator < (const num &b)const

	{

		return k < b.k;

	}

	int p[34],tot;

}w[MAXN];

bool check(num a,num b)

{

	if(a.tot < b.tot)swap(a,b);

	if(abs(a.tot - b.tot) != 1)return false;

	bool used = false;

	int i,j;

	for(i = 1,j = 1;i <= a.tot && j <= b.tot;++i,++j)

	{

		if(a.p[i] != b.p[j])

		{

			if(!used)

			{

				--j;

				used = true;

			}

			else

			{

				return false;

			}

		}

	}

	if(i == a.tot + 1 && j == b.tot + 1)return true;

	if(!used && (i == a.tot))return true;

	return false;

}

struct edge

{

	int to,nxt,f;

	ll w;

}e[MAXN + MAXN * MAXN + MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int f,ll w)

{

	e[edgenum] = (edge){b,lin[a],f, w};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-w};lin[b] = edgenum++;

	return;

}

int s,t;

ll d[MAXN];

int pre[MAXN],rate[MAXN];

bool v[MAXN];

#define INF 0x3f3f3f3f

#define NEG 0xc0c0c0c0c0c0c0c0

bool SPFA()

{

	queue<int> q;q.push(s);

	memset(d,0xc0,sizeof(d));d[s] = 0;

	rate[s] = INF;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] < d[k] + e[i].w && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].w;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return (d[t] != NEG);

}

int flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return rate[t];

}

int EK()

{

	int ans = 0;

	ll sum = 0;

	while(SPFA())

	{

		if(sum + d[t] * rate[t] >= 0)

		{

			sum += d[t] * rate[t];

			ans += rate[t];

			flow();

		}

		else

		{

			ans += sum / (-d[t]);

			break;

		}

	}

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&w[i].k);

	for(int i = 1;i <= n;++i)scanf("%d",&w[i].c);

	for(int i = 1;i <= n;++i)scanf("%lld",&w[i].v);

	sort(w + 1,w + 1 + n);

	for(int i = 1;i <= n;++i)

	{

		int x = w[i].k;

		w[i].tot = 0;

		for(int p = 2;p * p <= w[i].k;++p)

		{

			while(x % p == 0)

			{

				w[i].p[++w[i].tot] = p;

				x /= p;

			}

		}

		if(x != 1)w[i].p[++w[i].tot] = x;

	}

	s = n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)

	{

		if(w[i].tot % 2 == 0)

		{

			add(s,i,w[i].c,0);

		}

		else

		{

			add(i,t,w[i].c,0);

		}

		if(w[i].tot % 2 == 0)

		{

			for(int j = 1;j <= n;++j)

			{

				if(check(w[i],w[j]) || check(w[j],w[i]))

				{

					add(i,j,INF,w[i].v * w[j].v);

				}

			}

		}

	}

	cout << EK() << endl;

	return 0;

}