Codeforces 547A. Mike and Frog

大虐殺と聞いて。解法は教えてもらった。ムズすぎでは・・・

問題

高さh1のカエルと高さh2の花があり、1秒後にはカエルは高さが(x1*h1+y1) mod M、花は(x2*h2+y2) mod Mになる。
カエルの高さがa1、花の高さがa2に同時になるような最短時間を求めよ。そのような時間がなければ-1を返す。

2<=M<=10^6
0<=h1,h2,a1,a2,x1,x2,y1,y2

考え方

問題Aなので、パッと見、周期を求めて最小公倍数的な感じかと思うが、よく考える必要がある。

hがaとなる周期を考える。
(x*h+y) mod Mを愚直に計算していって、「①最初にaとなるタイミング」と「②次にaとなるタイミング」をみつければよい。見つからなければ解なし。
すると、aとなるタイミングというのは、「(②-①)*i+①, i>=0」のときaとなることがわかる。

「カエルがa1になるタイミング」と「花がa2になるタイミング」が同じになる最小の秒数を求めたい。
それぞれ「a*i+b」「c*j+d」(i>=0, j>=0)とする。
同じになるために「a*i+b == c*j+d」で無ければならないので、「i==(c*j+d-b)/a」となる整数i>=0,j>=0を探せばよい。

注意したいのは、aとcは0になる可能性があること。場合分けをする。
【a==0かつc==0】
b==dならbが答え。それ以外は解なし。

【a==0かつc>0】
b==c*j+dとなるjがあるかどうかなので、b>=dかつ(b-d)%c==0ならbが答え。それ以外は解なし。

【a>0かつc==0】
同様に、d>=bかつ(d-b)%a==0ならdが答え。それ以外は解なし。

【a>0かつc>0】
上記のjを探すことになる。しかし、ループを回すとして、「jをどこまで回せばよいか？」が問題になる。
i==(c*j+d-b)/aにおいて、jがaよりも大きいとすると、
i==(c*j -c*a+c*a + d-b)/a
i==(c*(j-a)+c*a+d-b)/a
i==(c*(j-a)+d-b)/a + c
となって、「jの結果」＝「(j-a)の結果+c」となり、
・「(j-a)の結果」が整数なら、「(j-a)の結果+c」は最小の秒数にはならない
・「(j-a)の結果」が整数じゃないなら、「(j-a)の結果+c」も整数じゃないなので、答えにはならない
ということがわかる。
(d-b)が負である可能性もあるので、「(j-a)の結果が負、+cすると0以上」も考慮すると、(c*j+d-b)が正となるjからa個分ループで確認し、最初に見つかったjを使って「c*j+d」が答えになる。見つからなければ解が存在しない、としてよい。

Editorial解

http://codeforces.com/blog/entry/18126

カエルの高さがa1になる秒数をみつけ、qとする。m秒経っても見つからなければ周期性から-1としてよい。もし、花のq秒後の高さがa2になるならそれが答え。
さらに、そこからa1の高さから次にa1になるまでにかかる時間をcとする。これもm秒経っても見つからなければ-1としてよい。

ここで、q秒後の花の高さをeとする。ここから考えると、c秒ごとにカエルの高さがa1になっているので、花の高さを確認するのもeからc秒後、2*c秒後、3*c秒後、・・・を確認すればよい。
これも花の高さは多くともm種類しかないはずなので、確認すべき秒数(i*c秒)もm回以下でよい。