山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[AtCoder Grand Contest 026] B - rng_10s

Java AtCoder

問題

f:id:yamakasa3:20180720204341p:plain

公式の解説を見たり、ブログを見たりしても理解できなかったので、自分の考えをかいてみます。

考え方

いくつかのブログによると、

$B \leq A$ , $C \leq B - 1$ , $B \leq D$

$f(n) = (A + Dn) \mod B$

( $n \geq 1$ )

が

$f(n) > C$

となるとジュースを買えなくなるらしいです。そうなの？という感じですが、この関数を考えることに集中します。

$B$ と $D$ の最大公約数を $g$ とします。

$g = \gcd (B, D)$

ここで、

$r_1 = Dn \mod B$

は

$0 \leq r_1 \leq B - 1$

ですが、最大公約数を考慮すると、 $D = gd$ , $B = gb$ を用いて、

$gdn = gbk + r_1$

$r_1 = g(dn - bk) = gm$

と表すことができます。

ここで、 $r_1$ の最大値を取る $m$ は

$r_1 = gm = gb - 1$ 　( $m = dn - bk$ )

$m = \lfloor b - \dfrac{1}{g} \rfloor = b - 1$

となります。したがって、 $m$ の取り得る値の範囲は、

$0 \leq m \leq b - 1$

となり、 $r_1$ の取り得る値は

$0, g, 2g, \cdots , (b - 1)g$

となります。つぎに、 $A$ について、

$r_2 = A \mod g$

$A = ga+ r_2$

$0 \leq r_2 \leq g - 1 \lt B$

とします。問題の関数は、

$f(n) = (A + Dn) \mod B$

$= \{ A \mod B + Dn \mod B\} \mod B$

$= \{ (ga + r_2) \mod B + gm \} \mod B$

$= \{ g(a + m) \mod B + r_2 \} \mod B$ 　　( $x \lt B$ ならば $x \mod B = x$ )

ここで、

$g(a + k) \mod B$ の最大値は $(b - 1)g = B - g$ であり、 $r_2$ の最大値は $g - 1$ であるので、

$g(a + k) \mod B + r_2 \lt B$

となるので、 $f(n)$ の最大値は

$f(n_{\max}) = B - g + r_2 = B - g + A \mod g$

となります。

感想

うーん。結構考えたんですが良く分かりませんでした。合同式を勉強する必要がありますね。

$g(a + k) \mod B$ の最大値は $(b - 1)g = B - g$ でありって所を端折ったんですが、

$l = a + k$ とすると

$gl \mod B$

を

$a \leq l \leq b + a - 1$

の範囲で考えるんですが、 $l$ の値は

$a , a + 1, \cdots , b + a - 1$

の値を取るので、 $m$ のときの議論と変わらないと思います。

$gl$ の値は $B$ を超えてもmodを取ったら循環しますしね。