ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC133 C - Remainder Minimization 2019

問題
提出コード

解法

基本的には、区間[L,R]から2つ数字i,jを選び、(i \times j) \ mod \  2019の最小値を求めていけばよいです。
が、このままだと_{R-L+1} C _{2} 回の計算が必要になってしまうので、この制約では間に合いません。
ここで、R-L+1の長さに注目すると、この長さが2019以上の際は、確実にi \  mod \  2019 0となるようなi区間の中に存在するはずです。
ということは、この数字を掛け算に利用することで、確実に(i \times j) \ mod  \ 20190にすることができます。
なので、結局

  • R-L+1が2019以上であれば答えは0

  • そうでなければ愚直に計算をして調べる

という操作を行ってあげればよいです。