ABC 296

D - M<=ab

https://atcoder.jp/contests/abc296/tasks/abc296_d

解説 AC。

条件より $X = ab \wedge X \geq M$ である。また $a,b$ は対称だから $a \leq b$ としても答えは変わらない。

\begin{align} M \leq X &= ab \Leftrightarrow \nonumber \\ \frac{M}{a} &\leq b \nonumber \\ \biggl\lceil \frac{M}{a} \biggr\rceil &\leq b \nonumber \\ \end{align}

$\lceil M/a \rceil$ は $b$ の下界だから $a \leq b$ と合わせて

\begin{align} &a \leq \biggl\lceil \frac{M}{a} \biggr\rceil \nonumber < \frac{M}{a} + 1 \nonumber \\ \Leftrightarrow ~ &a(a-1) < M \nonumber \end{align}

がいえる。よってせいぜいこの範囲の $a$ を探索すれば良い。

($a$ が $\sqrt{M}$ を超えると $a, b$ の大小関係が逆転する)

void solve() {
    ll N, M;
    cin >> N >> M;

    ll ans = INF;
    for (ll a = 1; a * a - a < M; a++) {
        ll b = (M + a - 1) / a;
        if (a <= N && b <= N) {
            chmin(ans, a * b);
        }
    }
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
}