高校数学で
「 を整数として は 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; } }