题目链接：https://cn.vjudge.net/contest/281959#problem/C
题目大意：中文题目
具体思路：用网络流的思想，我们求得是最大的匹配数，那么我们按照二分图的形式去建边就可以了，加上超级源点和超级汇点，就可以用网络流跑了。
建边的时候，我们首先把每个数进行素因子分解，看一下当前的这个数能够被分解成多少个素数，奇数个的放在一个数组里，偶数个的放在另一个数组里面（如果两个点直接能匹配的话，就需要他们两个相除之后只能剩余一个素数）。对于当前的这条边的权值，我们是按照最大流进行的，所以需要建立负边，具体的注释在代码中解释吧。
AC代码：
#include <iostream>
#include<stack>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
# define ll long long
const int maxn = +;
const int maxm = 3e5+;
const int mod = 1e9+;
const ll inf =1000000000000000ll;
struct node
{
int to;
ll cost;
ll w;
int nex;
} edge[maxm];
ll dis[maxm],prev[maxm],pree[maxm];
int vis[maxm];
int head[maxm],num;
ll t1[maxm],t2[maxm],t3[maxm];
ll tx[maxm],ty[maxm];
int viss[maxm],prim[maxm],primnum,isprim[maxm*];
void prime()
{
for(int i=; i<maxm; i++)
{
if(viss[i]==)
{
viss[i]=;
prim[++primnum]=i;
isprim[i]=;
for(int j=i; j<maxm; j+=i)
{
viss[j]=;
}
}
}
}
bool judge(ll t1,ll t2)
{
if(t1==||t2==)
return false;
if(t1<t2)
swap(t1,t2);
if(t1%t2!=)
return false;
t1/=t2;
// if(isprim[t1])
// return true;
// return false;
for(int i=;i<=primnum;i++){//判断是不是只剩下一个素数，这个地方有一个小的优化，我们看当前这个数是不是素数，只需要看到他的sqrt就可以了。
if(prim[i]>=t1)break;
if(t1%prim[i]==)return ;
}
return ;
}
void addedge(int fr,int to,ll w,ll cost)
{
edge[num].to=to;
edge[num].w=w;
edge[num].cost=-cost;
edge[num].nex=head[fr];
head[fr]=num++;
edge[num].to=fr;
edge[num].w=;
edge[num].cost=cost;
edge[num].nex=head[to];
head[to]=num++;
}
bool spfa(int st,int ed)
{
memset(vis,,sizeof(vis));
memset(pree,-,sizeof(pree));
for(int i=; i<=ed; i++)
dis[i]=inf;
dis[st]=,vis[st]=;
queue<int>q;
q.push(st);
while(!q.empty())
{
int top=q.front();
q.pop();
vis[top]=;
for(int i=head[top]; i!=-; i=edge[i].nex)
{
int tmp=edge[i].to;
if(edge[i].w&&dis[tmp]>dis[top]+edge[i].cost)
{
dis[tmp]=dis[top]+edge[i].cost;
pree[tmp]=top;
prev[tmp]=i;
if(vis[tmp]==)
{
vis[tmp]=;
q.push(tmp);
}
}
}
}
return pree[ed]!=-;
}
ll mincostflow(int st,int ed)
{
ll ans=;
ll cost=;
while(spfa(st,ed))
{
ll minn=inf ;
for(int i=ed; i!=st; i=pree[i])
{
minn=min(minn,edge[prev[i]].w);
}
if(cost+minn*dis[ed]<=)//注意这个地方，我们建立的是负边。
{
cost+=dis[ed]*minn;
ans+=minn;
for(int i=ed; i!=st; i=pree[i])
{
edge[prev[i]].w-=minn;
edge[prev[i]^].w+=minn;
}
}
else //寻找临界点
{
ans-=(cost/dis[ed]);
return ans;
}
}
return ans;
}
int main()
{
prime();
int n;
memset(head,-,sizeof(head));
scanf("%d",&n);
// cout<<primnum<<endl;
for(int i=; i<=n; i++)
{
scanf("%lld",&t1[i]);
}
for(int i=; i<=n; i++)
{
scanf("%lld",&t2[i]);
}
for(int i=; i<=n; i++)
{
scanf("%lld",&t3[i]);
}
int num1=,num2=;
for(int i=; i<=n; i++)//预先处理
{
int tmp=t1[i],tt=;
for(int j=; j<=primnum; j++)
{
while(tmp%prim[j]==)
{
tmp/=prim[j];
tt++;
}
if(tmp==||tmp==)
break;
}
if(tt&)
tx[++num1]=i;
else
ty[++num2]=i;
}
for(int i=; i<=num1; i++)
{
for(int j=; j<=num2; j++)
{
if(judge(t1[tx[i]],t1[ty[j]]))
{
addedge(tx[i],ty[j],1e9,t3[tx[i]]*t3[ty[j]]);
}
}
}
for(int i=; i<=num1; i++)
{
addedge(,tx[i],t2[tx[i]],);
}
for(int i=; i<=num2; i++)
{
addedge(ty[i],n+,t2[ty[i]],);
}
ll ans=mincostflow(,n+);
printf("%lld\n",ans);
return ;
}