Description

凡是考智商的题里面总会有这么一种消除游戏. 不过现在面对的这关连连看可不是 QQ 游戏里那种考眼力的游戏. 我们的规则是, 给出一个闭区间 \([a, b]\) 中的全部整数, 如果其中某两个数 \(x, y\) (设 \(x \gt y\)) 的平方差 \(x^2 - y^2\) 是一个完全平方数 \(z^2\), 并且 \(y\) 与 \(z\) 互质, 那么就可以将 \(x\) 和 \(y\) 连起来并且将它们一起消除, 同时得到 \(x + y\) 点分数. 那么过关的要求就是, 消除的数对尽可能多的前提下, 得到足够的分数. 快动手动笔算一算吧.

Input

只有一行, 两个整数, 分别表示 \(a, b\).

Output

两个数, 可以消去的对数, 及在此基础上能得到的最大分数.

Sample Input

1 15

Sample Output

2 34

Data Range

对于 30% 的数据,\(1 \leq a, b \leq 100\)

对于 100% 的数据,\(1 \leq a, b \leq 1000\)

Explanation

将一个点拆成两个点, 一个入, 一个出.

但是要考虑, 我们不能只是为了判重而单向连点, 这样会造成最后的费用比预想的要小一些 或者出了偏差. 严格意义上讲, 我们应该连两次 (例如两个点 \(i, j\), 那么我们应该在图上连接 \(i \rightarrow j, j \rightarrow i\)) , 然后把最后的答案除以二.

用 SPFA 费用流跑可以水过......

@MisakiHanayo 表示将 dist[] 数组只开成 1010 是一个巨大的错误~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;
typedef long long int lli;
const int maxn = 4010, maxm = 101000;
const int infinit = 0x0f7f7f7f;

class SpfaMaxFlow
{
public:
    struct edge
    {
        int u, v, flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v, int flow, int cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    int dist[maxn], inque[maxn];
    edge *from[maxn];
    bool spfa(void)
    {
        for (int i = 1; i <= n; i++)
            dist[i] = -infinit, inque[i] = false, from[i] = NULL;
        queue<int> que;
        que.push(s);
        inque[s] = true, dist[s] = 0;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[ep->v] < dist[p] + ep->cost) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            inque[p] = false;
        }
        if (dist[t] > 0)
            return true;
        return false;
    }
    int max_flow, max_cost;
    void eval(void)
    {
        max_flow = 0;
        max_cost = 0;
        while (spfa()) {
            int tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u]) {
                ep->flow -= tmp;
                ep->rev->flow += tmp;
                max_cost += ep->cost * tmp;
            }
            max_flow += tmp;
        }
        return ;
    }
} graph;

int a, b;

int gcd(int x, int y)
{
    if (y == 0)
        return x;
    return gcd(y, x % y);
}

bool judge(int x, int y)
{
    if (x < y) swap(x, y);
    int z_2 = x*x - y*y;
    int z = sqrt(z_2);
    if (z * z != z_2)
        return false;
    return gcd(y, z) == 1;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &a, &b);
    graph.n = 2002;
    graph.s = 2001;
    graph.t = 2002;
    int sz = b - a + 1;
    for (int i = a; i <= b; i++) {
        // Connecting node to source and sink
        graph.add_edge(graph.s, 2*i - 1, 1, 0);
        graph.add_edge(2*i, graph.t, 1, 0);
        // Connecting between nodes
        for (int j = a; j <= b; j++)
            if (i != j && judge(i, j))
                graph.add_edge(2*i - 1, 2*j, 1, i + j);
    }
    graph.eval();
    printf("%d %d\n", graph.max_flow / 2, graph.max_cost / 2);
    return 0;
}