UOJ12 猜数

问题描述

这一天,小Y、小D、小C正在愉快地玩耍。

小Y是个数学家,他一拍脑袋冒出了一个神奇的完全平方数 $n$。

小D是个机灵鬼,很快从小Y嘴里套出了 $n$ 的值。然后在脑内把 $n$ 写成了 $a×b$的形式。其中 $a,b$都是正整数。

小C是个八卦狂,他发现小D从小Y那里获知了神奇的东西,于是死缠烂打追问小D。最后小D说道:“我可以告诉你正整数 $g$ 和 $l$ 的值,我保证 $ab=gl=n$ 且 $a,b$ 都是$g$的倍数。但是 $a,b$ 我可不能告诉你。”
这可急坏了小C。他决定退而求其次,找出$a+b$的最小值和最大值。请你帮帮他吧!

做法

因为$n=ab$,根据均值不等式,$a+b$最小值在$a=b=\sqrt{gl}$时取到,所以$a+b$最小值为$2\sqrt{gl}$
注意$g,l<=10^18$,不能直接乘了开根号(除非你用long double),所以可以写成$\sqrt{\frac{l}{g}}×g$
因为$ab=gl=n$,$a,b$为g的倍数,所以$a+b$的最大值在$a=b$,$g=l$时取到,这显然合法,所以最大值就是$g+l$

核心代码

1
2
3
4
5
6
7
8
long long a,b;
int t;
t=read();
while(t){
--t;
scanf("%lld%lld",&a,&b);
printf("%lld %lld\n",(long long)(sqrt(b/a)+0.5)*a*2,a+b);
}
# UOJ

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×