记录编号	362964	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 数字配对	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2017-01-09 18:27:42	内存使用	5.49 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZEN=33015;
struct Rabit_math{
	int prime[SIZEN/5],cnt,N;bool check[SIZEN];
	Rabit_math(){
		int i,j;N=SIZEN-10,cnt=0;check[1]=true;
		for(i=2;i<N;i++){
			if(!check[i])prime[++cnt]=i;
			for(j=1;j<=cnt;j++){
				if(i*prime[j]>N)break;
				check[i*prime[j]]=true;
				if(i%prime[j]==0)break;
			}
		}
	}
	bool cot(int n){
		bool res=false;
		for(int i=1;i<=cnt&&prime[i]<=n;i++)
			while(n%prime[i]==0)n/=prime[i],res^=true;
		if(n^1)res^true;
		return res;
	}
	bool is(int n){
		if(n<N)return !check[n];
		for(int i=1;i<=cnt;i++)
			if(n%prime[i]==0)return false;
		return true;
	}
}MA;
#define LL long long
const int maxn=205,maxm=maxn*maxn<<1,INF=0x3f3f3f3f;
const LL inf=1ll<<50;
struct Rabit_tree{int to,next,c,f;LL dis;}e[maxm<<1];
int n,m,head[maxn],len=1,S,T,a[maxn],c[maxn];bool bl[maxn];
void Rabit_Set(int prt,int son,int cap,LL dis){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,
	e[len].c=cap,e[len].f=0,e[len].dis=dis;
}
void Rabit_set(int prt,int son,int cap,LL dis){
	//if(dis)printf("%d %d\n",prt,son);
	Rabit_Set(prt,son,cap,-dis),Rabit_Set(son,prt,0,dis);
}
#define to e[i].to
int q[(maxn+maxm)<<2],vis[maxn],tim=0;bool bein[maxn];LL dis[maxn];
bool Rabit_run(){
	int s,t,rt,i;q[s=t=1]=S,bein[S]=true;
	for(i=1;i<=T;i++)dis[i]=inf;dis[S]=0;
	while(s<=t){
		rt=q[s++],bein[rt]=false;
		for(i=head[rt];i;i=e[i].next)
			if(dis[to]>dis[rt]+e[i].dis&&e[i].c>e[i].f){
				dis[to]=dis[rt]+e[i].dis;
				if(!bein[to])bein[to]=true,q[++t]=to;
			}
	}
	return dis[T]^inf;
}
int Rabit_run(int rt,int v){
	if(rt==T||!v)return v;
	int flow=0,tmp;vis[rt]=tim;
	for(int i=head[rt];i;i=e[i].next)
		if(vis[to]^tim&&dis[to]==dis[rt]+e[i].dis){
			tmp=Rabit_run(to,min(v,e[i].c-e[i].f));
			if(tmp>0){
				flow+=tmp,v-=tmp,e[i].f+=tmp,e[i^1].f-=tmp;
				if(!v)break;
			}
		}
	return flow;
}
int Rabit_zkw(){
	LL cost=0;int i,flow=0,tmp;
	while(Rabit_run())
		while(tim++,tmp=Rabit_run(S,INF)){
			cost+=tmp*1ll*dis[T];
			if(cost>0){cost-=tmp*1ll*dis[T],flow+=-cost/dis[T];return flow;}
			else flow+=tmp;
		}
	return flow;
}
void Rabit_in(){
	scanf("%d",&n);int i,j,b;S=n+1,T=n+2;
	for(i=1;i<=n;i++)scanf("%d",&a[i]),bl[i]=MA.cot(a[i]);
	for(i=1;i<=n;i++){
		scanf("%d",&b);
		if(bl[i])Rabit_set(S,i,b,0);
		else Rabit_set(i,T,b,0);
	}
	for(i=1;i<=n;i++)scanf("%d",&c[i]);
	for(i=1;i<=n;i++)if(bl[i])
		for(j=1;j<=n;j++)if(!bl[j]){
			if(a[i]%a[j]==0&&MA.is(a[i]/a[j]))Rabit_set(i,j,INF,c[i]*1ll*c[j]);
			if(a[j]%a[i]==0&&MA.is(a[j]/a[i]))Rabit_set(i,j,INF,c[i]*1ll*c[j]);
		}
}
int main(){
	freopen("menci_pair.in","r",stdin);freopen("menci_pair.out","w",stdout);
	Rabit_in();
	printf("%d\n",Rabit_zkw());
}