cf-edu-146b

发布时间 2023-04-07 11:11:41作者: 安潇末痕

题目链接:https://codeforces.com/contest/1814/problem/B

只有残缺的思路,还不足以解决这道题。

完整思路:对于一个数x来说,如果一个数a除以它的余数为y,商为z,所需步数为y+z+(x-1),那么反过来(x变为它的商,z为除数,所需步数依然是不变的,可以举几个例子看看,易得。),所以我们只需要枚举\(n^(1/2)之前的数,取最小值即为答案。\)

证明:不太会,等会看看官方题解。

代码:

#include <bits/stdc++.h>
using namespace std;
vector<int>fac;
void solve(){
    fac.clear();
    int a,b;
    cin>>a>>b;
    int ans = a+b;
    for (int x=1;x<=200000;x++){
        int temp = x-1+a/x+b/x;
        if (a%x) temp++;
        if (b%x) temp++;
        ans = min(ans,temp);
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    T = 1;
    cin>>T;
    while(T--) solve();
    return 0;
}