题目如下：

题目链接

题解 or 思路：

我们可以发现我们有两个可选的入手方向：
1.正推
2.反推
我们可以发现正推似乎看不出来什么东西，而反推可以发现一个性质！
性质如下：
我们假设最终的腿长为 $M$
可以得到下面的等式：
cnt=⌈aM⌉+⌈bm⌉+M−1cnt = \\left\\lceil\\dfrac{a}{M}\\right\\rceil + \\left\\lceil\\dfrac{b}{m}\\right\\rceil + M -1cnt=⌈Ma​⌉+⌈mb​⌉+M−1

首先我们将腿变成 $M$ 需要 $M-1$ 次操作
假设：
$a\mathrm{mod}M=x$
$a\mathrm{mod}M=y$
一定有：
$x<M$
$y<M$

我们可以操作 $2$ 次就可以完成各自除剩余的那一部分
然后我们的腿长就会先变到 $M$
最后走完剩下的路程
⌈aM⌉+⌈bM⌉\\left\\lceil\\dfrac{a}{M}\\right\\rceil + \\left\\lceil\\dfrac{b}{M}\\right\\rceil⌈Ma​⌉+⌈Mb​⌉

所以易得：
cnt=⌈aM⌉+⌈bM⌉+M−1cnt = \\left\\lceil\\dfrac{a}{M}\\right\\rceil + \\left\\lceil\\dfrac{b}{M}\\right\\rceil + M -1cnt=⌈Ma​⌉+⌈Mb​⌉+M−1

我们通过枚举 $M$ 来找 cntMincnt_{Min}cntMin​

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话，可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \\ios::sync_with_stdio(false); \\cin.tie(0);
// #define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 100009;
//int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int a, b;
void solve()
{cin >> a >> b;int ans = inf;for (int i = 1; i <= 50000; i++)ans = min(ans, (a + i - 1) / i + (b + i - 1) / i + i - 1);cout << ans << '\\n';
}
int main()
{buff;int _ = 1;cin >> _;while (_--)solve();
}

zd软件