[uoj 12][UER #1]猜数

本题真正的难点不是在结论上（确信

题目链接

http://uoj.ac/problem/12

题解

为方便起见，不妨设 \(a \leq b\)。

众所周知有个好东西叫均值不等式。

$$\frac{a+b}{2} \geq \sqrt{ab}$$

这个不等式取到等号当且仅当 \(a=b\)。

于是 \(a+b\) 的最小值当然是 \(2 \sqrt{gl}\)。

\(a+b\) 的最大值呢？因为 \(g \leq a \leq \sqrt{gl}\)，显然可知当 \(a=g,b=l\) 时取到最大值 \(g+l\)。

当然本题的难点其实不在上面（

如果直接计算 \(\sqrt{gl}\)，当 \(g,l \leq 10^{18}\) 精度无法承受。

我们可以这样计算：

1. 令 \(p=\gcd(g,l)\)，\(x=g/p\)，\(y=l/p\)。
2. 这时候可以证明 \(x,y\) 均为完全平方数（原因？可以用反证法，这里略去）。
3. 因此 \(\sqrt{gl}=p \sqrt{x} \sqrt{y}\)。

#include <cmath>
#include <iostream>
using namespace std;
long long gcd(long long x,long long y)
{
 return y==0?x:gcd(y,x%y);
}
long long calc(long long x,long long y)
{
 long long p=gcd(x,y);
 x/=p,y/=p;
 return p*(long long)sqrt(x)*(long long)sqrt(y);
}
int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  long long g,l;
  cin>>g>>l;
  cout<<2*calc(g,l)<<' '<<g+l<<endl;
 }
 return 0;
}