[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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注