ABC133 C - Remainder Minimization 2019

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os

MOD = 2019


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    L, R = list(map(int, sys.stdin.readline().split()))
    ret = float('inf')

    if R - L >= 2019:
        print(0)
        exit()

    for i in range(L, R+1):
        for j in range(i+1, R+1):
            ret = min(ret, (i * j) % MOD)

    print(ret)


if __name__ == '__main__':
    main()

考え方

    if R - L >= 2019:
        print(0)
        exit()

LとRの差が2019以上(R - L >= 2019)のとき、
iまたはjには2019の倍数(2019 * n)が存在している。
つまり、あまりが0になるため、回答も0になる。

あとはそれ以外のパターンを普通に算出する。
LとRの差が2019以上の場合は最初にはじいているため、
その後の処理は2019の2乗程度の計算量になる。