ABC133-C Remainder Minimization 2019
問題
ABC133-C Remainder Minimization 2019
非負整数$L$,$R$に対し、整数$i$,$j$を$L \leq i < j \leq R$となるように選んだときの$(i \times j) \mod 2019$の最小値を求める
$0 \leq L < R \leq 2 \times 10^{9}$
方針
愚直にやると $O((R-L)^2)$で死ぬ
$i$,$j$については、$i = 2019a + b, j = 2019c + d$となる非負整数$a, b, c, d(0 \leq b,d \leq 2018)$が存在する
そのことから$i \times j = 2019^2ac+2019(ad+bc)+bd$を$2019$で割ったあまりは$bd$を$2019$で割ったあまりとなる
$b$,$d$は$0 \leq b,d \leq 2018$であるため、$i$,$j$についてそれぞれ$2019$個、すなわち$2019^2$通り調べればよいということになる
$2019^2 = 4076361$なので十分に間に合う。
感想
300点問題にしては難しい気がします