1 /************************************************************** 2     Problem: 2661 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:128 ms 7     Memory:3984 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 using namespace std;15 const int N = 2005;16 const int M = N * 100;17 const int inf = (int) 1e9;18  19 struct edges {20     int next, to, f, cost;21     edges() {}22     edges(int _n, int _t, int _f, int _c) : next(_n), to(_t), f(_f), cost(_c) {}23 } e[M];24   25 int n, S, T;26 int first[N], tot = 1;27 int d[N], g[N], q[N];28 bool v[N];29  30    31 inline void Add_Edges(int x, int y, int f, int c) {32     e[++tot] = edges(first[x], y, f, c), first[x] = tot;33     e[++tot] = edges(first[y], x, 0, -c), first[y] = tot;34 }35   36 inline int calc() {37     int flow = inf, x;38     for (x = g[T]; x; x = g[e[x ^ 1].to])39         flow = min(flow, e[x].f);40     for (x = g[T]; x; x = g[e[x ^ 1].to])41         e[x].f -= flow, e[x ^ 1].f += flow;42     return flow;43 }44   45 bool spfa() {46     int x, y, l, r;47     for (x = 1; x <= T; ++x)48         d[x] = inf;49     d[S] = 0, v[S] = 1, q[0] = S;50     for(l = r = 0; l != (r + 1) % N; ++l %= N) {51         for (x = first[q[l]]; x; x = e[x].next)52             if (d[q[l]] + e[x].cost < d[y = e[x].to] && e[x].f) {53                 d[y] = d[q[l]] + e[x].cost, g[y] = x;54                 if (!v[y])55                     q[++r %= N] = y, v[y] = 1;56             }57         v[q[l]] = 0;58     }59     return d[T] != inf;60 }61  62 inline void work() {63     int ans1 = 0, ans2 = 0, del;64     while (spfa()) {65         del = calc();66         ans1 += del, ans2 += del * d[T];67     }68     printf("%d %d\n", ans1 >> 1, -ans2 >> 1);69 }70  71 inline int sqr(int x) {72     return x * x;73 }74  75 inline int gcd(int a, int b) {76     return b ? gcd(b, a % b) : a;77 }78  79 inline bool check(int a, int b) {80     int t = sqr(b) - sqr(a);81     if (sqr((int) sqrt(t)) != t) return 0;82     return gcd(a, (int) sqrt(t)) == 1;83 }84  85 int main() {86     int a, b, i, j;87     scanf("%d%d", &a, &b);88     S = (b - a + 1) << 1 | 1, T = S + 1;89     for (i = a; i <= b; ++i)90         for (j = a; j < i; ++j) if (check(j, i))91             Add_Edges(i - a + 1, j + b - a * 2 + 2, 1, - i - j),92             Add_Edges(j - a + 1, i + b - a * 2 + 2, 1, - i - j);93     for (i = a; i <= b; ++i)94         Add_Edges(S, i - a + 1, 1, 0), Add_Edges(i + b - a * 2 + 2, T, 1, 0);95     work();96     return 0;97 }