[AtCoder Grand Contest 026] B - rng_10s
問題
公式の解説を見たり、ブログを見たりしても理解できなかったので、自分の考えをかいてみます。
考え方
いくつかのブログによると、
, ,
()
が
となるとジュースを買えなくなるらしいです。そうなの?という感じですが、この関数を考えることに集中します。
と の最大公約数を とします。
ここで、
は
ですが、最大公約数を考慮すると、, を用いて、
と表すことができます。
ここで、 の最大値を取るは
()
となります。したがって、 の取り得る値の範囲は、
となり、 の取り得る値は
となります。つぎに、について、
とします。問題の関数は、
( ならば )
ここで、
の最大値はであり、の最大値は であるので、
となるので、の最大値は
となります。
感想
うーん。結構考えたんですが良く分かりませんでした。合同式を勉強する必要がありますね。
の最大値はでありって所を端折ったんですが、
とすると
を
の範囲で考えるんですが、 の値は
の値を取るので、 のときの議論と変わらないと思います。
の値は を超えてもmodを取ったら循環しますしね。