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