ABC133 C - Remainder Minimization 2019 解説

C - Remainder Minimization 2019

atcoder.jp

くじかつで死んだので戒めに書きます

問題

整数L Rが与えられるのでL≤i<j≤Rかつ(i×j)mod 2019の最小値を求める。

解法

L Rの間に2019の倍数がある場合、mod2019で0になることが確定する。

でも判定がめんどいのでR-Lが2019以上なら0で確定する。

それ以外の場合L Rのmod2019を取ってその間でi jを全探索すればよい。(mod 2019を取るのでL Rのmod2019を取っても結果は変わらず探索範囲が狭まる)

ソースコード

cdef:
  int l, r, ans=2020
l,r=map(int,input().split())
if r-l>=2019:
  print(0);exit()
l%=2019
r%=2019
if l>r:
  l,r=r,l
for i in range(l,r):
  for j in range(i+1,r+1):
    ans=min(ans,i*j%2019)
print(ans)

精進します...