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

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

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

高校数学で

 n を整数として  n(n+1)(n+2) は 3 の倍数であることを示せ」

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

問題へのリンク

問題概要

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;
    }
}