はまやんはまやんはまやん

hamayanhamayan's blog

Remainder Minimization 2019 [AtCoder Beginner Contest 133 C]

https://atcoder.jp/contests/abc133/tasks/abc133_c

解説

https://atcoder.jp/contests/abc133/submissions/6313028

300点問題にしては難しい問題に見える。
(i×j) % 2019 = (i % 2019) * (j % 2019)
となる。
理論的な最小値は0であり、これを目指すことを考える。
i % 2019をiを増やしながら考えていくと、2019個以内に0になるものが存在する。
よって、全探索していき、答えが0になったら、その時点で返せば、ひどい計算量にはならない。
全探索するときは、intの範囲を超える可能性があるので、それぞれ剰余をとってからかけるかlong longを使おう。

int L, R;
//---------------------------------------------------------------------------------------------------
int solve() {
	int ans = inf;
	rep(i, L, R) rep(j, i + 1, R + 1) {
		chmin(ans, (int)(1LL * i * j % 2019));
		if (ans == 0)return 0;
	}
	return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> L >> R;
	cout << solve() << endl;
}