AtCoder ABC 133 C - Remainder Minimization 2019 - あるエンジニアのAtCoder奮闘記

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()

公式解説にもあるように、 $a$ を $2019$ で割った余りと $b$ を $2019$ で割った余りが同じならば、 $a\times c$ を $2019$ で割った余りと $b\times c$ を $2019$ で割った余りが同じであることが言えます。そのため $i,j$ について $2019$ で割った余りについてのみ考えればよく、考えるべき $i,j$ の組は高々 $2019^2$ 程度となります。