[ABC296D] M<=ab 题解

lottle1212 · 2023-04-03 21:07:06 · 题解

[ABC296D] M<=ab

Part0：

首先解读一下题目：

给出两个整数 N 和 M (1 \leq N, M \leq 10 ^ {12})。
找出两个整数 a 和 b (1 \leq a, b \leq N) 的积，使得 a \times b \geq M（a, b 可以相同），求出其中最小的积。

输入：

5 7

输出：

在此样例中，a,b 分别为 2,4，2 \times 4 = 8 \geq 7。

Part1：

由于所求的 a \times b \geq M，因此，我们就很容易想到从小到大枚举 a，再求出最小的 b，若 a <= n && b <= n，则此对 a,b 满足条件，更新答案。

AC Code:

#include<bits/stdc++.h>
using namespace std;
long long n, m, ans = 1e18, i, j;
signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(i = 1; i * i <= m; ++ i) {//枚举i
        j = m / i + (m % i != 0);//求出最小的j
        if(i <= n && j <= n) ans = min(ans, i * j);//若i，j满足均条件，更新答案
    }
    cout << (ans == 1e18 ? -1 : ans);//若答案未被更新，输出-1；否则输出求得的最小值
    return 0;
}

注：i,j 即 a,b。

Part2：

提交以上代码，你就会发现 WA on #16。请看此样例：

输入：

4 15

输出：

而原来的代码就会输出：

-1

在此样例中，a,b 分别为 4,4。但在原先的代码中， a 只会枚举到 \sqrt{15}，也就是 3。当 a = 3 时，b = 5，即 b 不满足条件（前面的 b 就更不可能满足条件啦），结果就~~华丽地~~输出了 -1。

解决此问题也十分容易。由于原来的代码在枚举 a 时离正确答案小了那么一点点，因此，我们只需要将 for 循环中的 m 改成 m * 2，即可轻松通过此题。

真正的 AC Code：

#include<bits/stdc++.h>
using namespace std;
long long n, m, ans = 1e18, i, j;
signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(i = 1; i * i <= m * 2; ++ i) {//注意此处要乘2
        j = m / i + (m % i != 0);
        if(i <= n && j <= n) ans = min(ans, i * j);
    }
    cout << (ans == 1e18 ? -1 : ans);
    return 0;
}