题目描述

难度分:$999$

输入$n$，$m(1 \leq n,m \leq 10^{12})$。

选两个不超过$n$的正整数$a$和$b$，使得$a \times b$至少为$m$。

输出$a \times b$的最小值。如果不存在这样的$a$和$b$，输出$-1$。

输入样例$1$

5 7

输出样例$1$

8

输入样例$2$

2 5

输出样例$2$

-1

输入样例$3$

100000 10000000000

输出样例$3$

10000000000

算法

数学

在$[1,n]$的范围内遍历$a$的可能取值，对于某个$a$，要想$a \times b \geq m$，则$b$至少要为$[\frac{b+a-1}{a}]$（$\frac{b}{a}$的向上取整），其中$[.]$为对$.$的向下取整操作。而此时我们可以发现，如果老老实实遍历完$a$，那$n \leq 10^{12}$一定会超时。因此还需要用$m$进一步限制范围，由于$a \times b$最小限度超过$m$就可以了，所以$a^2$不会超过$m$太多，只需要遍历到$O(\sqrt{m})$这个量级。

按照以上的准则得到$a$和$b$的候选，在$b \leq n$时维护$a \times b$的最小值即可。

复杂度分析

时间复杂度

主要受到外层循环的限制，时间复杂度为$O(min(n, \sqrt{m}))$。

空间复杂度

只使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>

using namespace std;
typedef long long LL;

LL n, m;

int main() {
    scanf("%lld%lld", &n, &m);
    LL x = LLONG_MAX;
    for(LL a = 1; a <= n && a*a <= m*2; a++) {
        LL b = (m + a - 1)/a;     // 此时要保证a*b>=m，b至少为这个数
        if(b <= n) {
            x = min(x, a*b);
        }
    }
    if(x == LLONG_MAX) x = -1;
    printf("%lld\n", x);
    return 0;
}