【pythonでABC133を解説】C - Remainder Minimization 2019

問題概要

問題ページ

問題文

非負整数 \(L, R\) が与えられます。
\(2\) つの整数 \(i, j\) を \(L \leq i < j \leq R\) を満たすように選びます。
\((i \times j) \mbox{ mod } 2019\) の最小値を求めてください。

制約

• 入力は全て整数
• \(0 \leq L < R \leq 2 \times 10^9\)

問題の考察

とりあえず、\(L,R\)の全ての組み合わせを全列挙した場合を考えてみる。

計算量は\(O(\sum_{i = L}^{ R} (R-i))\)で、\(L=0,R=2 \times 10^9\)の時に最大となり全然間に合わないことが分かる。（計算しなくても\(\times 10^9\)の時点で無理）

考察のポイントとしては、\((i \times j) \mbox{ mod } 2019\)の最小値は確実に0以上で、\(0\)のなったらその時点で計算を終了してしまって問題ないというところ。

また、\(i,j\)をそれぞれ順番に処理していった場合に\(2019\)の倍数が少なくとも\(2019\times 2019=4,076,361\)回に1個存在するのは直感的に分かると思います。（\(2019\)は素数じゃないので実際は\(2019\)の倍数はもっと存在します。）

これならpythonでも十分に間に合うはずです。

たびすけ

\(i,j\)を順番に処理して\((i \times j) \mbox{ mod } 2019\)が\(0\)になった時点で計算を終了すればpythonでも十分に間に合います。

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    l, r = list(map(int, input().rstrip('\n').split()))
    t = 10 ** 20
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            t = min(t, (i * j) % 2019)
            if t == 0:
                print(t)
                exit()
    print(t)


if __name__ == '__main__':
    solve()