#P2661. [BeiJing wc2012]连连看

    ID: 1718 传统题 1000ms 128MiB 尝试: 1570 已通过: 564 难度: 7 上传者: 标签>CF2300提高+/省选-暴力枚举欧几里得算法二分图判定二分图建模最小费用最大流势能优化费用流Dijkstra费用流最大费用最大流

[BeiJing wc2012]连连看

题目描述

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

输入格式

只有一行,两个整数,分别表示 aa,bb。

输出格式

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

样例 #1

样例输入 #1

1 15

样例输出 #1

2 34

提示

数据规模与约定

  • 对于 30%30\% 的数据,保证 1≤a,b≤1001\le a,b\le100。
  • 对于 100%100\% 的数据,保证 1≤a,b≤10001\le a,b\le1000。