容易想到是最小割（最大权独立集）
然后每个数拆成两个点，不能同时选的之间连边跑最小割，
最后答案=总数-mincut/2 因为这样建图将流量变成了原来的两倍
当然这道题更好的建图方法是分成奇数和偶数两个集合
不难发现，奇数和奇数，偶数和偶数之间显然不能同时满足条件的
所以这样直接ans=总点数-mincut
const inf=;
type node=record
point,flow,next:longint;
end; var edge:array[..] of node;
a,p,cur,pre,d,numh,h:array[..] of longint;
s,i,j,n,t,len:longint;
x:double; function gcd(a,b:longint):longint;
begin
if b= then exit(a)
else exit(gcd(b,a mod b));
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var q,u,i,j,neck,tmp:longint;
begin
sap:=;
u:=;
numh[]:=t+;
for i:= to t do
cur[i]:=p[i];
neck:=inf;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
pre[j]:=u;
cur[u]:=i;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
tmp:=t;
i:=p[u];
q:=-;
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then
if h[j]<tmp then
begin
tmp:=h[j];
q:=i;
end;
i:=edge[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
cur[u]:=q;
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
t:=*n+;
for i:= to n do
begin
read(a[i]);
add(,i,a[i]);
add(i,,);
add(i+n,t,a[i]);
add(t,i+n,);
s:=s+a[i];
end;
for i:= to n- do
for j:=i+ to n do
begin
x:=sqrt(sqr(a[i])+sqr(a[j]));
if (gcd(a[i],a[j])=) and (x=trunc(x)) then
begin
add(i,j+n,inf);
add(j+n,i,);
add(j,i+n,inf);
add(i+n,j,);
end;
end;
writeln(s-sap div );
end.