UOJ12 【UER #1】猜数 题解

题目链接：#12. 【UER #1】猜数

题意：

给定一个完全平方数 $n=a\times b=g \times l$ ，其中 $a,b,g,l$ 均为正整数。

每次给出 $g,l$ ，求 $a + b$ 的最小值和最大值，保证 $g \mid a$ 且 $g \mid b$ 。

根据均值不等式，有 $a + b \ge 2\sqrt{ab} = 2\sqrt{n}$ 。

由于 $n=gl$ 是完全平方数，我们可以求得 $\sqrt{n}$ 的值，得到 $a + b$ 的下界，当 $a=b=\sqrt{n}$ 时等号成立。

那么当 $g \mid a,~g\mid b$ 时还能取到等号吗？

设 $a = a_0g,~b = b_0g$ ，则 $n = a_0b_0g^2$ ，则 $l = a_0b_0g$ ，故 $g \mid l$ 。

设 $l = kg$ ，则 $gl = kg^2$ 为完全平方数，故 $k$ 也为完全平方数。

设 $k=t^2$ ，则 $l = t^2g$ ，那么 $a = b = \sqrt{n} = tg$ ，是 $g$ 的倍数，那么等号可以取到，最小值得到。

考虑最大值，由于 $a + b = a + \frac{n}{a}$ ，显然这是一个在 $[g,l]$ 上的对勾函数，如下图所示：

那么当 $a=g$ 或 $a=l$ 时取到最大值，此时 $a + b = g + l$ ，且显然有 $g \mid a, g\mid b$ 。

注意这道题的 $g,l$ 非常大，可以利用 $g \mid l$ ，那么 $\sqrt{gl} = tg = \sqrt{t^2}g = g\sqrt{\frac{l}{g}}$ 求根号。

实际上不一定要 $g \mid l$ ，设求 $\sqrt{xy}$ （$\sqrt{xy}$ 是整数）记 $d = \gcd(x, y),~x = x_0d,y = y_0 d$ 。

那么此时显然 $\gcd(x_0, y_0) =1$ 。显然 $x_0,y_0$ 都是完全平方数，直接分别开方后乘上 $d$ 即可

时间复杂度 $\mathcal{O}(T \log V)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())

int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int sqrt(int x, int y)
{
    int d = gcd(x, y), m = sqrtl(x / d), n = sqrtl(y / d);
    return d * n * m;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--)
    {
        static int a, b; cin >> a >> b;
        cout << sqrt(a, b) * 2 << ' ' << a + b << '\n';
    }
    return 0;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/uoj12.html