ABC296D题解

发布时间 2023-08-25 21:17:13作者: osfly

简单题。

考虑 -1 的情况,即为 \(n^2<m\)

剩下暴力枚举 \(a\) 即可。上限为 \(\sqrt{m}+1\)。注意要 \(+1\),因为上取整(本人赛时被这个罚了很多次)。

可以由 \(m\)\(a\) 确定 \(b\) 的最小值,即 \(b=\lceil\frac{m}{a}\rceil\)

注意卡 long long 以及 \(a,b\) 的最大值不能超过 \(n\)

时间复杂度 \(O(\sqrt{m})\)。(原来手误打错,感谢管理员指出qwq)

#include<cstdio>
#include<cmath>
#define ll unsigned long long
ll n,m;
ll ans=1ll<<64-1;
ll min(ll a,ll b)
{
    return a<b?a:b;
}
ll a,b;
int main()
{
    scanf("%llu%llu",&n,&m);
    if(n*n<m) printf("-1");
    else if(n*n==m) printf("%llu",n*n);
    else if(m<=n) printf("%llu",m);
    else
    {
        for(a=1;a<=sqrtl(m)+1&&a<=n;a++)
        {
            b=m/a;
            if(a*b<m) b++;
            if(b<=n&&a*b==m)
            {
                ans=m;
                break;
            }
            if(b<=n&&a*b>m) ans=min(ans,a*b);
        }
        printf("%llu",ans);
    }
    return 0;
}