けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 296 D - M<=ab (1Q, 緑色, 400 点)

AtCoder AtCoder400点 ABC-D 緑色diff 数学(整数問題) 全探索 多重for文 【問題集】整数変数の式で表された条件を扱う探索 約数 考察：一部の変数を固定して考える O(√N)まで考えれば十分 入力が定数個 x以上の最小のNで割ってr余る整数を求める 見積り大事 NoviSteps1Q

「ある量を固定して考えるとよい」「 \sqrt{M} まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね！

問題概要

正の整数 N, M が与えられる。

M 以上の整数のうち、 1 以上 N 以下の 2 つの整数 a, b の積 ab として書ける最小の整数を求めよ。

そのような整数が存在しない場合は -1 を出力せよ。

制約

  • 1 \le N, M \le 10^{12}

Step 1：まず問題の意味を掴む

問題の意味がパッと分かりづらいので、まずは問題の意味を掴むところから始めよう。入力例 1 を見てみる。

N = 5, M = 7 のとき。

この場合、 7 は答えにはならない。なぜなら、 7 は素数なので 7 = 1 \times 7 という分解しかない。つまり、 7 は 5 以下の整数の積としては表せないのだ。

7 の次の数である 8 は条件を満たす。 8 = 2 \times 4 と分解できて、 2 も 4 も 5 以下の整数なので OK。よって答えは 8 である。

ここから、次のような解法が思い浮かぶかもしれない (これだと TLE するはず......)

n = M, M+1, M+2, \dots を順に試していき、

  • M = a \times b を満たす a, b を列挙する (これは、約数列挙によって O(\sqrt{M}) でできる)
  • a, b \le N となるような a, b を見つけたら、探索を打ち切って n を出力する

しかし、この解法だと、 O(\sqrt{M}) の計算量を要する処理を、 n = M, M+1, M+2, \dots と探索していくので、かなり時間がかかってしまう。

　

Step 2： a \le b と仮定して、 a を固定する

ここで典型テクニックを使う。まず、 a \le b という仮定を入れることにする。問題文の条件は、 a と b に関して対称なので、 a \le b というように大小関係を仮定しても差し支えない。高校数学でもお馴染みのテクニックだ。

そしてもう一つ、極めて重要な典型手法を使う。それは「ある 1 つの変数を固定して考える」というものだ。緑色 diff 以上の問題で頻出の考え方だ。今回は a を固定して考えることにしよう。

仮に a の値を決めたならば、次のように考えればよい。

  • M を a で割って、小数点以下を切り上げた値を b とする
  • このとき、 ab は、 a の倍数であるような最小の M 以上の整数となる (ただし、 a, b \le N という条件に注意)

なんと、 a の値を決め打ちすると、最適解が容易に求められるのだ。あとは、さまざまな a の値を試していけばよい。

　

Step 3： a の範囲を見積もる

最後に、 a の値として、どの範囲を探索すればよいかを考えよう。

ここで、 A = \lceil \sqrt{M} \rceil ( \sqrt{M} 以上の最小の整数) とする。注意したいことは、 a = A, b = A とした場合の ab = A^{2} は、最適解の候補であることである。よって、 A^{2} より大きい値が最適解になることはない。

このことから、実は、 a \ge A + 1 の範囲を試す必要はないことが言える。なぜならば、もし a \ge A+1 であるとすると、 a \le b より、

ab \ge a^{2} \ge (A+1)^{2}

となるからだ。先ほど、 A^{2} より大きい値が最適解になることはないという結論を導いたばかりなので、 a \ge A + 1 の範囲を試す必要はないことがわかった。

よって、 a = 1, 2, \dots, A について試せば十分だと分かった。

まとめ

解法をまとめる。

A = \lceil \sqrt{M} \rceil とする。

各 a = 1, 2, \dots, \min(N, A) について、以下の値を求めて、その最小値をとる。

  • M を a で割って、小数点以下を切り上げた値を b とする
  • b \le N であるならば、 M' = ab が a を固定したときの最小解である

計算量は O(\min(N, \sqrt{M})) と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<60;

int main() {
    long long N, M;
    cin >> N >> M;
    long long res = INF;
    for (long long a = 1; a <= N; ++a) {
        // a の倍数のうち、M 以上である最小の整数を求める
        long long b = (M + a - 1) / a;
        if (b <= N) res = min(res, a * b);
        
        // a <= ceil(√M) としてよい
        if (a * a > M) break;
    }
    if (res == INF) cout << -1 << endl;
    else cout << res << endl;
}