记录编号	267911	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 数字配对	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2016-06-11 19:07:08	内存使用	1.39 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=210;
const int maxm=40010;
long long INF=1000000000000000LL;
int cnt=1,fir[maxn],nxt[maxm],to[maxm],ID[maxn],path[maxn],n;
long long a[maxn],b[maxn],c[maxn],cost[maxm],cap[maxm],dis[maxn],val[maxm];

void addedge(int a,int b,long long c,long long v){
    nxt[++cnt]=fir[a];to[cnt]=b;cap[cnt]=c;val[cnt]=v;fir[a]=cnt;
}

int S,T;
long long Spfa(){
    queue<int>q;
    q.push(S);
    for(int i=S;i<=T;i++)
    	dis[i]=-INF;dis[S]=0;
    while(!q.empty()){
        int node=q.front();q.pop();
        for(int i=fir[node];i;i=nxt[i])
            if(cap[i]&&dis[node]+val[i]>dis[to[i]]){
                dis[to[i]]=val[i]+dis[node];
                path[to[i]]=i;
                q.push(to[i]);
            }
    }
    
    return dis[T]==-INF?INF:dis[T]; 
}

long long Aug(){
    int p=T;
    long long f=INF;
    while(p!=S){
        f=min(f,cap[path[p]]);
        p=to[path[p]^1];
    }
    p=T;
    while(p!=S){
        cap[path[p]]-=f;
        cap[path[p]^1]+=f;
        p=to[path[p]^1];
    }
    return f;
}

long long MCMF(){
    long long ret=0,now=0,c,d;
    while((d=Spfa())!=INF){
		c=Aug();
		if(c*d+now<0)
			return ret-now/d;
		else{ret+=c;now+=c*d;}
	}
    return ret;    
}


bool Get_ID(int x){
	bool ret=true;
	for(int i=2,m=(int)sqrt(x);i<=m;i++)
		if(x%i==0){while(x%i==0)x/=i,ret=!ret;}
	if(x!=1)ret=!ret;
	return ret;	
}

bool IS_Prime(int x){
	for(int i=2,m=(int)sqrt(x);i<=m;i++)
		if(x%i==0)return false;
	return true;	
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("menci_pair.in","r",stdin);
	freopen("menci_pair.out","w",stdout);
#endif
	scanf("%d",&n);S=0;T=n+1;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
	for(int i=1;i<=n;i++)ID[i]=Get_ID(a[i]);
	for(int i=1;i<=n;i++){
		if(!ID[i]){
			addedge(S,i,b[i],0);addedge(i,S,0,0);
			for(int j=1;j<=n;j++)
				if(ID[j]){
					long long x=a[i],y=a[j];if(x<y)swap(x,y);
					if(x%y==0&&IS_Prime(x/y)){
						addedge(i,j,INF,c[i]*c[j]);
						addedge(j,i,0,-c[i]*c[j]);
					}
				}
		}
		else{addedge(i,T,b[i],0);addedge(T,i,0,0);}
	}
	printf("%lld\n",MCMF());
	return 0;
}