AtCoder ABC 133 C - Remainder Minimization 2019 (300 点)

高校数学で

「 を整数として は 3 の倍数であることを示せ」

という問題はよくあったと思う。これは「連続する 3 整数には 3 の倍数が含まれる」というのが理由になっている。今回こんな感じのことを考える。

問題へのリンク

問題概要

2 つの整数 があたえられる。 を満たす と に対する を 2019 で割ったあまりの最小値を求めよ。

制約

• 

考えたこと

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

しかし今回は とかなので、このままだとダメ。そこで工夫を考えることになる。

工夫

例えば , とかだったら、 とかにすれば、 は 2019 で割り切れるのであまりを 0 にできる！！！！！

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

• のときは答えが 0
• それ以外のときは、全探索できる！！！候補数は多く見積もっても くらいなので。

となる。下の実装上は安全のため、「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;
    }
}