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