Description
有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。
若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数，
那么这两个数字可以配对，并获得 ci×cj 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 0 的前提下，求最多进行多少次配对。
Input
第一行一个整数 n。
第二行 n 个整数 a1、a2、……、an。
第三行 n 个整数 b1、b2、……、bn。
第四行 n 个整数 c1、c2、……、cn。
Output
一行一个数，最多进行多少次配对
Sample Input
3
2 4 8
2 200 7
-1 -2 1
2 4 8
2 200 7
-1 -2 1
Sample Output
4
HINT
n≤200，ai≤10^9，bi≤10^5，∣ci∣≤10^5
Source
鸣谢Menci上传
主要是要注意到质因数有几个（2^2算两个），这样个数为奇数只能与个数为偶数配对，个数为偶数只能和个数为奇数配对，然后就是一个二分图，随便建一建图跑最大费用流就好。
program rrr(input,output);
const
inf=;
type
etype=record
t,c,next,rev:longint;
w:int64;
end;
var
e:array[..]of etype;
num,a,d,q,fre,frv:array[..]of longint;
s:array[..]of boolean;
p:array[..]of longint;
c,dis:array[..]of int64;
inq:array[..]of boolean;
n,m,i,j,x,b,cnt,h,t,ans:longint;
w,f:int64;
function min(a,b:int64):int64;
begin
if a<b then exit(a) else exit(b);
end;
procedure ins(x,y,c:longint;w:int64);
begin
inc(cnt);e[cnt].t:=y;e[cnt].c:=c;e[cnt].w:=w;e[cnt].next:=a[x];a[x]:=cnt;
end;
procedure add(x,y,c:longint;w:int64);
begin
ins(x,y,c,w);e[cnt].rev:=cnt+;ins(y,x,,-w);e[cnt].rev:=cnt-;
end;
procedure spfa;
begin
for i:= to n do dis[i]:=-inf;dis[]:=;
h:=;t:=;q[]:=;inq[]:=true;
while h<>t do
begin
inc(h);if h> then h:=;
i:=a[q[h]];
while i<> do
begin
if (e[i].c>) and (dis[q[h]]+e[i].w>dis[e[i].t]) then
begin
dis[e[i].t]:=dis[q[h]]+e[i].w;
fre[e[i].t]:=i;frv[e[i].t]:=q[h];
if not inq[e[i].t] then
begin
inc(t);if t> then t:=;
q[t]:=e[i].t;inq[e[i].t]:=true;
end;
end;
i:=e[i].next;
end;
inq[q[h]]:=false;
end;
end;
begin
assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);
fillchar(s,sizeof(s),true);s[]:=false;
for i:= to do if s[i] then
begin
j:=i+i;while j<= do begin s[j]:=false;j:=j+i; end;
end;
m:=;for i:= to do if s[i] then begin inc(m);p[m]:=i; end;
readln(n);
for i:= to n do read(num[i]);
for i:= to n do
begin
x:=num[i];j:=;d[i]:=;
while x> do begin while x mod p[j]= do begin inc(d[i]);x:=x div p[j]; end;inc(j);if j>m then break; end;
if x> then inc(d[i]);
end;
fillchar(a,sizeof(a),);cnt:=;
for i:= to n do begin read(b);if d[i] mod = then add(i,n+,b,) else add(,i,b,); end;
for i:= to n do read(c[i]);
for i:= to n do for j:=i+ to n do
if (abs(d[i]-d[j])=) and ((num[i] mod num[j]=) or (num[j] mod num[i]=)) then
begin
if d[i] mod = then add(j,i,,c[i]*c[j]) else add(i,j,,c[i]*c[j]);
end;
ans:=;inc(n);w:=;
while true do
begin
spfa;
if dis[n]=-inf then break;
i:=n;f:=;
while i<> do begin f:=min(f,e[fre[i]].c);i:=frv[i]; end;
if w+f*dis[n]< then begin ans:=ans+w div (-dis[n]);break; end
else begin ans:=ans+f;w:=w+f*dis[n]; end;
i:=n;while i<> do begin dec(e[fre[i]].c,f);inc(e[e[fre[i]].rev].c,f);i:=frv[i]; end;
end;
write(ans);
close(input);close(output);
end.