其实稍加思考发现$(i,j)$能连边,如果以它们的质因子个数为准的话,这其实是个二分图。

那么题目就变成了最大费用流,由于spfa的值会越来越小,只要在费用小于$0$时候停止就好了。

可以很形象地理解成交易市场,$i$带着$B_i$的筹码,从起点来,$j$带着$B_j$的筹码,从终点来,它们能交易$\min\{B_i,B_j\}$。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,Max=1e9,M=1010;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
bool v[N];
int calc(int x)
{
    int ret=0;
    for(int i=2;1ll*i*i<=x;i++)
        while(x%i==0)x/=i,++ret;
    if(x!=1)++ret;return ret;
}
struct edge{int y,c,next;ll d;}a[N<<1];int last[M],len;
void ins(int x,int y,int c,ll d)
{
    a[++len]=(edge){y,c,last[x],d};last[x]=len;
    a[++len]=(edge){x,0,last[y],-d};last[y]=len;
}
int A[M],B[M],C[M],n,st,ed,w[N];
void prepare()
{
    len=1;st=n+1,ed=st+1;
    for(int i=1;i<=n;i++)w[i]=calc(A[i]);
    for(int i=1;i<=n;i++)
        if(w[i]&1)
        {
            ins(st,i,B[i],0);
            for(int j=1;j<=n;j++)if(i!=j)
            {
                if(A[j]%A[i]==0&&w[j]==w[i]+1)ins(i,j,min(B[i],B[j]),1ll*C[i]*C[j]);
                else if(A[i]%A[j]==0&&w[i]==w[j]+1)ins(i,j,min(B[i],B[j]),1ll*C[i]*C[j]);
            }
        }
        else ins(i,ed,B[i],0);
}
int f[N],q[N],prv[N];ll d[N];
bool spfa()
{
    memset(v,0,sizeof(v));
    memset(f,0,sizeof(f));f[st]=0x3f3f3f3f;memset(d,0xcf,sizeof(d));int l=1,r=2;q[1]=st;v[st]=1;d[st]=0;
    while(l!=r)
    {
        int x=q[l++];v[x]=0;if(l==n+3)l=1;
        for(int k=last[x],y;k;k=a[k].next)
        {
            y=a[k].y;
            if(d[y]<d[x]+a[k].d&&a[k].c)
            {
                d[y]=d[x]+a[k].d;
                f[y]=min(f[x],a[k].c);
                prv[y]=k;
                if(!v[y]){v[y]=1;q[r++]=y;if(r==n+3)r=1;}
            }
        }
    }
    return f[ed];
}
ll ans=0,s=0;
void del()
{
    int y=ed,k=prv[y],ret=0;
    while(k)
    {
        a[k].c-=f[ed];
        a[k^1].c+=f[ed];
        k=prv[a[k^1].y];
    }
    s+=d[ed]*f[ed];
    if(s<0)ret=(-s)/(-d[ed])+(!((-s)%(-d[ed])==0));
    ans+=f[ed]-ret;
}
int main()
{
    qr(n);
    for(int i=1;i<=n;i++)qr(A[i]);
    for(int i=1;i<=n;i++)qr(B[i]);
    for(int i=1;i<=n;i++)qr(C[i]);
    prepare();
    while(spfa()&&s>=0)
        del();
    qw(ans);puts("");
    return 0;
}