🌊

ABC133 C - Remainder Minimization 2019のメモ

2023/10/16に公開

AtCoder

競プロ

tech

わからんので解説を見ました。

解説を見て

2019 で割った余りが同じであるような 2 数 a, b について、(a×c) mod 2019
と (b × c) mod 2019 は必ず同じ値になります。

たしかにそうかも。具体的な数で考えてみます。iを5で固定してみると、jは6以上の数です。i = 5, j = 6の場合は積は30で、2019で割った数も30です。j = 7にすると35となり、5ずつ増えていきます。j = 403のときは2015まで増えて、j = 404で積は2020となり% 2019は1になります。ここで一巡しましたが、今度はここから6、11、16と増えていきます。もう少し増えると31、36となって、最初に挙げたのとは違う周期になっていることがわかります。
このまま5ずつ増えるのでいずれは2016となり、積が2021となってここで% 2019は2となります。ここから7、12と増えていくのでまた違う周期となりました。一巡するたびに1ずつずれていくようです。周期が変わるたびに新たな数が出現するようになるので、少なくともまた30、35と増えていく周期になるまでの範囲は調べる必要があります。逆にいえばその範囲だけ調べれば十分ということですね。
では元の周期に戻るのはどの地点かというと、それが解説に書かれていることですね。(a×c) mod 2019と (b × c) mod 2019ですが、これは(c × a) mod 2019と (c × b) mod 2019と考えても同じはずです。今回はc = 5, a = 6で考えていたことなります。ではbは何かというと、2019で割った数が同じなので、たとえば2025があり得ます。この場合の(c × b) mod 2019は、(5 × 2025) % 2019です。5 × 2025は10125で、2019で割った余りは30です。これは(c × a) mod 2019、つまり(5 × 6) mod 2019と一致します。なるほど、なのでi = 5だとしたら2024まで探索すれば十分ということですね。2025というのは6に2019を足して求めた数でして、つまり(i + 2019 - 1)まで調べればいいということになります。

ただ、これはi = 5と固定した場合の話なので、他にもi = 6のケース、i = 7のケースなど一通り調べる必要があります。ただ、解説にある通りでこのように考えた時の最大のケース数は $2019^2$ の4076361通りだけなので、これは単純に全部調べればいいということですね。

実装

Lが最小のiなので、iは(L + 2019 - 1)までとなります。ただ、Rがそれより小さいかもしれないのでminをとりました。
jはiより大きいので最小のjは(i + 1)です。そこから(i + 2019 - 1)まで調べます。同じくminをとっています。
（untilを使うことで、明示的に-1はしなくて済んでいます）

答えとしてあり得るのは0～2018なのでansは別にLongでなくてもいいのですが、Intだとmin(ans, (i * j) % 2019 )のところで型の不一致ということでコンパイルエラーになるのでLongにしちゃいました。

import kotlin.math.min

fun main() {
    val (l, r) = readln().split(" ").map { it.toLong() }

    var ans = Long.MAX_VALUE

    for(i in l until min(r, l + 2019)) {
        for(j in i + 1 until min(r + 1, i + 2019)) {
            ans = min(ans, (i * j) % 2019 )
        }
    }
    println(ans)
}

（執筆時間: 28分42秒）

解説を見て

実装

Discussion