http://www.lydsy.com/JudgeOnline/problem.php?id=2661
思路:预处理出每个数字，然后若有x^2=y^2+z^2且z与y互质，
s->x 1 ,0
x+n-> t 1 , 0
x->y+n -> 1 , inf-x-y
y->x+n-> 1 ,inf-x-y
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define inf 1000000
int l,r,pd[],L[],R[],cnt,sz,b[];
int tot,go[],next[],first[],cost[],flow[];
int op[],dis[],c[],vis[],edge[],from[];
int S,T,ans1,ans2;
int gcd(int a,int b){if (b==) return a;else return gcd(b,a%b);}
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y,int z,int l){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
flow[tot]=z;
cost[tot]=l;
}
void add(int x,int y,int z,int l){
insert(x,y,z,l);op[tot]=tot+;
insert(y,x,,-l);op[tot]=tot-;
}
bool spfa(){
for (int i=;i<=T;i++)
dis[i]=inf,vis[i]=;
int h=,t=;c[]=S;vis[S]=;dis[S]=;
while (h<=t){
int now=c[h++];
for (int i=first[now];i;i=next[i]){
int pur=go[i];
if (dis[pur]>dis[now]+cost[i]&&flow[i]){
dis[pur]=dis[now]+cost[i];
edge[pur]=i;
from[pur]=now;
if (vis[pur]) continue;
vis[pur]=;
c[++t]=pur;
}
}
vis[now]=;
}
return dis[T]!=inf;
}
void updata(){
int mn=0x3f3f3f3f;
for (int i=T;i!=S;i=from[i]){
mn=std::min(mn,flow[edge[i]]);
}
for (int i=T;i!=S;i=from[i]){
ans2+=mn*cost[edge[i]];
flow[edge[i]]-=mn;
flow[op[edge[i]]]+=mn;
}
ans1+=mn;
}
int main(){
l=read();r=read();
if (l>r) std::swap(l,r);
for (int i=;i<=;i++) pd[i*i]=i;
for (int j=l;j<=r;j++)
for (int i=j+;i<=r;i++){
int k=i*i-j*j;
if (pd[k]&&gcd(pd[k],j)==){
b[i]=b[j]=;
cnt++;
L[cnt]=j;
R[cnt]=i;
}
}
for (int i=l;i<=r;i++)
if (b[i])
b[i]=++sz;
S=;T=sz+sz+;
for (int i=l;i<=r;i++)
if (b[i])
add(S,b[i],,),add(b[i]+sz,T,,);
for (int i=;i<=cnt;i++){
add(b[L[i]],b[R[i]]+sz,,inf-L[i]-R[i]);
add(b[R[i]],b[L[i]]+sz,,inf-L[i]-R[i]);
}
while (spfa()) updata();
printf("%d ",ans1/);
printf("%d\n",(ans1*inf-ans2)/);
}