jiry_2's Blog

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即可。