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が合成数ということを問題を解く前に知ってしまったので、どうせならと思いそれを踏まえた解説を考えていたのですが、別に合成数かどうかはあまり関係ありませんでしたね。
雑記
- ネタが尽きているので言語アップデートが待ち遠しいです。