[AtCoder] ABC 133 C – Remainder Minimization 2019

2019年7月7日

問題

方針

区間 \( [L, R]\) を全探索する必要はなく、\( [L, \min(R, L + 2019) ]\) の範囲を調べればよいです。これは、

\[ f(x) = x \bmod 2019\]

という関数を考えると、\( 0 \leq f(x) \leq 2018 \ (L \leq x \leq L + 2019)\) となるからです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll L, R;
  cin >> L >> R;
  ll v = 2019;
  ll m = L + min(R - L, 2019ll);
  for (ll i = L; i <= m - 1; i++) {
    for (ll j = i + 1; j <= m; j++) {
      ll t = (i % 2019) * (j % 2019);
      t %= 2019;
      v = min(t, v); 
    }
  }
  cout << v << "\n";
  return 0;
}