あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC 133 C - Remainder Minimization 2019

irisruneです。求められるレベルが上がっている感じがあるので競プロの勉強もしたいですが、他にも勉強するべきことがあるので大変ですね。

問題

atcoder.jp

うっかりすると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()

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

あとは単純に取り得るすべての組み合わせについてi\times jの剰余を求めて最小値を出力すればいいだけなのですが、変に計算量を減らそうと考えると剰余が最小となるi,jの組み合わせについて求めればよいだけと考えてしまうかもしれません。 しかしこれは2つの理由で正しくありません。

1つ目は、2019が合成数であるということです。例えば、i=3,j=673のときにi\times j=2019となり剰余が0となります。これによってi,jともに剰余が0でなくとも積の剰余が0となることがあります。

2つ目は、そもそもの考え方が間違っているということです。単純に、i=2,j=1010のときにi\times j=2020となり剰余が1となります。i,jの剰余が最小ならば積の剰余が最小となるという前提が間違っているのでこの方法は取れません。

2019が合成数ということを問題を解く前に知ってしまったので、どうせならと思いそれを踏まえた解説を考えていたのですが、別に合成数かどうかはあまり関係ありませんでしたね。

雑記

  • ネタが尽きているので言語アップデートが待ち遠しいです。