問題概要

2 つの整数 $L, R$ があたえられる。 $L \le x \lt y \le R$ を満たす $x$ と $y$ に対する $xy$ を 2019 で割ったあまりの最小値を求めよ。

制約

$0 \le L \lt R \le 2 \times 10^{9}$

考えたこと

整数問題っぽいけど、こういうのはまずは「単純な全探索できないか...」と考えるのがよさそう。今回でいえば単純な全探索は二重ループでできそう。

しかし今回は $L, R \le 2 \times 10^{9}$ とかなので、このままだとダメ。そこで工夫を考えることになる。

工夫

例えば $L = 10$ , $R = 3000$ とかだったら、 $x = 2019$ とかにすれば、 $xy$ は 2019 で割り切れるのであまりを 0 にできる！！！！！

あまりは 0 よりは小さくならない。で、よく考えると「2019 個以上の整数が連続すると、その中に必ず 2019 の倍数がある」というのが言える。よって

$R - L \ge 2019$ のときは答えが 0
それ以外のときは、全探索できる！！！候補数は多く見積もっても $(R - L)^{2}$ くらいなので。

となる。下の実装上は安全のため、「R - L > 3000 なら 0」としている。

#include <iostream>
using namespace std;

int main() {
    long long L, R; cin >> L >> R;
    if (R - L > 3000) cout << 0 << endl;
    else {
        long long res = 2018;
        for (long long i = L; i < R; ++i)
            for (long long j = i+1; j <= R; ++j)
                res = min(res, (i * j) % 2019);
        cout << res << endl;
    }
}