program p2661; type bian=record next,point,w,f:longint; end; var d,p,after:array[0..5000] of longint; x:array[1..500000] of longint; pd:array[0..5000000] of boolean; b:array[0..40000] of bian; tot,len,a,c,i,j:longint; procedure ade(k1,k2,k3,k4:longint); begin inc(len); b[len].point:=k2; b[len].next:=p[k1]; b[len].f:=k3; b[len].w:=k4; p[k1]:=len; end; procedure add(k1,k2,k3,k4:longint); begin ade(k1,k2,k3,k4); ade(k2,k1,0,-k4); end; function gcd(k1,k2:longint):longint; begin if k2=0 then exit(k1); exit(gcd(k2,k1 mod k2)); end; function min(k1,k2:longint):longint; begin if k1<k2 then exit(k1) else exit(k2); end; function spfa:boolean; var head,now,i,j:longint; begin head:=1; now:=0; fillchar(pd,sizeof(pd),false); fillchar(after,sizeof(after),-1); fillchar(x,sizeof(x),0); fillchar(d,sizeof(d),$3f); x[1]:=0; d[0]:=0; pd[0]:=true; while head>now do begin inc(now); i:=p[x[now]]; while i<>-1 do begin j:=b[i].point; if (d[j]>d[x[now]]+b[i].w) and (b[i].f>0) then begin d[j]:=d[x[now]]+b[i].w; after[j]:=i; if pd[j]=false then begin pd[j]:=true; inc(head); x[head]:=j; end; end; i:=b[i].next; end; pd[x[now]]:=true; end; if after[c+1]=-1 then exit(false) else exit(true); end; function change:longint; var num,ans,i,j:longint; begin ans:=maxlongint; i:=c+1; j:=after[i]; while j<>-1 do begin ans:=min(b[j].f,ans); i:=b[j xor 1].point; j:=after[i]; end; num:=0; i:=c+1; j:=after[i]; tot:=tot+ans; while j<>-1 do begin num:=num+ans*b[j].w; dec(b[j].f,ans); inc(b[j xor 1].f,ans); i:=b[j xor 1].point; j:=after[i]; end; exit(num); end; function dinic:longint; var num:longint; begin num:=0; while spfa=true do num:=num+change; exit(num); end; function max(k1,k2:longint):longint; begin if k1<k2 then exit(k2) else exit(k1); end; begin readln(a,c); len:=-1; tot:=0; fillchar(p,sizeof(p),-1); fillchar(b,sizeof(b),0); for i:=a to c do for j:=a to c do if (trunc(sqrt(abs(i*i-j*j)))=sqrt(abs(i*i-j*j))) and (i<>j) then begin if gcd(trunc(sqrt(abs(i*i-j*j))),min(i,j))=1 then add(i,c+j,1,-i-j); end; for i:=a to c do begin add(0,i,1,0); add(i+c,c*2+1,1,0); end; c:=c*2; i:=-dinic; writeln(tot div 2,' ',i div 2); end.
把所有点拆成两个,做一次gcd,把所有满足条件之间的点连上边,构成一个二分图,流量为1,费用为-(x+y),求这个图的最小费用最大流,费用取反然后均除以2即可。