AtCoder ABC 133 C - Remainder Minimization 2019
irisruneです。求められるレベルが上がっている感じがあるので競プロの勉強もしたいですが、他にも勉強するべきことがあるので大変ですね。
問題
うっかりするとWAを出してしまうこともあるかと思いましたが…気のせいかもしれません。実装はB問題より軽いです。
import sys import math import numpy as np INF = 1000000000 MOD = 2019 def input(): return sys.stdin.readline().rstrip() def main(): l, r = [int(e) for e in input().split()] ans = INF for i in range(l, min(l + MOD, r + 1)): for j in range(i + 1, min(l + MOD, r + 1)): ans = min(ans, ((i % MOD) * (j % MOD)) % MOD) print(ans) main()
公式解説にもあるように、をで割った余りとをで割った余りが同じならば、をで割った余りとをで割った余りが同じであることが言えます。そのためについてで割った余りについてのみ考えればよく、考えるべきの組は高々程度となります。
あとは単純に取り得るすべての組み合わせについての剰余を求めて最小値を出力すればいいだけなのですが、変に計算量を減らそうと考えると剰余が最小となるの組み合わせについて求めればよいだけと考えてしまうかもしれません。 しかしこれは2つの理由で正しくありません。
1つ目は、2019が合成数であるということです。例えば、のときにとなり剰余が0となります。これによってともに剰余が0でなくとも積の剰余が0となることがあります。
2つ目は、そもそもの考え方が間違っているということです。単純に、のときにとなり剰余が1となります。の剰余が最小ならば積の剰余が最小となるという前提が間違っているのでこの方法は取れません。
2019が合成数ということを問題を解く前に知ってしまったので、どうせならと思いそれを踏まえた解説を考えていたのですが、別に合成数かどうかはあまり関係ありませんでしたね。
雑記
- ネタが尽きているので言語アップデートが待ち遠しいです。