mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #305 (Div. 1) A. Mike and Frog

解法

基本的には公式の解説通り。
http://codeforces.com/blog/entry/18126

ただ途中でやってる
g(g(...(g(x))))

c = 1, d = 0
for i = 1 to c
     c = (cX) % p
     d = (dX + Y) % p

Then,

f(x)
     return (cx + d) % p

というのが一瞬「?」だったのでそこだけ補足。

まずcとかdが初期変数になってますがそこからいきなりわかりづらい。cってもう使ってるでしょっていう。こう直しました。

P = 1, Q = 0
for i = 1 to c
     P = (cX) % p
     Q = (dX + Y) % p

Then,

f(x)
     return (Px + Q) % p

なんでこれで上手く行くのかについて説明します。

ここでやりたいのは更新式
h_2 = (x_2h_2+y_2) mod m
をc回行ったら最初のh_2の値に応じて最終的なh_2の値はどうなるか?ということを求めたいです(更新式は上に貼った解説のページの変数ではなく問題文にあるような変数の定義の仕方をしています)。これを求めるために,「定数項の部分」と「初期値(h_2)に依存する部分」に分けて値を求めてみます。

定数項の部分はよく考えると,毎回今までの定数項の部分をx_2倍してその後y_2だけ足す,ということを繰り返しているだけです。なので,上の式で言うとQを計算し続けるだけで定数項の部分を求めることが出来ます。

次に,「初期値に依存する部分」です。こちらは,次のように考えています。「仮に,初期値が1だとして計算してみる。上記の更新式は線形なので1の場合がわかれば一般のxについてはx倍するだけで初期値を求められる。」
ということで,初期値が1の場合を考えてみると,これは毎回x_2倍するだけなので上の式のPを計算し続けると初期値に依存した項が求められます。

const ll INF = 1ll<<55;

ll solve(ll m, ll h1, ll a1, ll x1, ll y1, ll h2, ll a2, ll x2, ll y2) {
    ll q = INF;
    {
        ll now = h1;
        for (ll i = 1; i <= m; i++) {
            now = (x1*now+y1) % m;
            if (now == a1) q = min(q, i);
        }
    }
    if (q == INF) return -1;
    ll e = h2;
    for (ll i = 1; i <= q; i++) {
        e = (x2*e+y2) % m;
    }
    if (e == a2) return q;
    ll c = INF;
    {
        ll now = a1;
        for (ll i = 1; i <= m; i++) {
            now = (x1*now+y1) % m;
            if (now == a1) c = min(c, i);
        }
    }
    if (c == INF) return -1;
    ll P = 1, Q = 0;
    for (int i = 0; i < c; i++) {
        P = P*x2%m;
        Q = (x2*Q+y2) % m;
    }
    for (ll i = 1; i <= m; i++) {
        e = (P*e+Q) % m;
        if (e == a2) return q+c*i;
    }
    return -1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll m, h1, a1, x1, y1, h2, a2, x2, y2;
    cin >> m;
    cin >> h1 >> a1;
    cin >> x1 >> y1;
    cin >> h2 >> a2;
    cin >> x2 >> y2;
    cout << solve(m, h1, a1, x1, y1, h2, a2, x2, y2) << endl;
    return 0;
}