ABC133 C問題：Remainder Minimization 2019

問題. Remainder Minimization 2019

非負整数 が与えられる． を求めよ．

制約：

解法

任意の非負整数 に対して，
　
となるので，任意の に対しては で を満たす が存在する．したがって，調べるべき区間は で十分であることが分かる．したがって，この区間は高々 2019 個の整数しか含まないので全探索をしても間に合う．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ll L, R;
    cin >> L >> R;

    ll min_v = 2018;
    R = min(L + 2018, R);
    for (ll i = L; i < R; ++i)
        for (ll j = i + 1; j <= R; ++j)
            min_v = min(min_v, (i * j) % 2019);

    cout << min_v << endl;

    return 0;
}

だいぶ迷ってしまった．剰余の演算の性質とかよく使うのにパッと出てこないのはどうしたらいいんだろう．