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

問題文

http://codeforces.com/contest/547/problem/A

解法

mod を取っているので，それぞれ高々 m 回でループするのはすぐわかる．
とりあえずそれぞれについて目的の高さになるまで愚直にシミュレートする．
この時到達できないならそもそも不可能なので -1．
よって以降はどちらも到達可能であると仮定する．
さらに，現時点で同時刻にどちらも目的の高さになっているならそれが答えなので，そうなっていないと仮定する．
ひとまずカエルを目的の高さになるまで進める（時間 t1 でそうなるとする）と，それ以降はサイクルの大きさ（c1 とおく）の倍数時間だけ進めたときのみ，カエルは目的の高さになっていることがわかる．
ただし，目的の高さに到達可能であっても，サイクル上に目的の高さがないなら不可能であり，この場合は -1 を出力する必要がある．
あとはこの c1 回の遷移を1まとまりとした写像 f を構築して，花のほうに適用するだけでよい．
不可能でないなら，これも高々 m 回でループするはずである．
もし cnt 回目の f の適用で花が目的の高さになったなら，答えは t1 + c1 * cnt となる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll inf = 1e18;

int main() {
    int m;
    vector<ll> h(2), a(2), x(2), y(2);
    cin >> m;
    for(int i = 0; i < 2; ++i) {
        cin >> h[i] >> a[i] >> x[i] >> y[i];
    }

    vector<ll> t(2), cycle_sz(2);
    bool on_cycle = false;
    for(int i = 0; i < 2; ++i) {
        vector<ll> d(m, inf);
        d[h[i]] = 0;
        ll cur = h[i];
        while(true) {
            const ll nxt = (x[i] * cur + y[i]) % m;
            if(d[nxt] != inf) {
                cycle_sz[i] = (d[cur] - d[nxt] + 1);
                if(i == 0) {
                    on_cycle = d[a[i]] != inf && d[a[i]] >= d[nxt];
                }
                break;
            }
            d[nxt] = d[cur] + 1;
            cur = nxt;
        }
        t[i] = d[a[i]];
    }

    if(t[0] == inf || t[1] == inf) {
        cout << -1 << endl;
        return 0;
    }
    if(t[0] == t[1]) {
        cout << t[0] << endl;
        return 0;
    }
    if(!on_cycle) {
        cout << -1 << endl;
        return 0;
    }

    ll A = 1, B = 0; // calc (f^cycle[0])(x) = Ax + B
    for(int i = 0; i < cycle_sz[0]; ++i) {
        auto nA = (A * x[1]) % m;
        auto nB = (y[1] + x[1] * B) % m;
        A = nA, B = nB;
    }

    ll cur_h2 = h[1];
    for(int i = 0; i < t[0]; ++i) {
        cur_h2 = (x[1] * cur_h2 + y[1]) % m;
    }

    ll cnt = 0;
    while(cur_h2 != a[1] && cnt < m) {
        cur_h2 = (cur_h2 * A + B) % m;
        cnt += 1;
    }

    if(cnt < m && cur_h2 == a[1]) {
        cout << t[0] + cycle_sz[0] * cnt << endl;
    } else {
        cout << -1 << endl;
    }
}

感想

算数に対する基礎体力がなくて手こずりまくった．
サイクルの上にいないなら NG ということに不覚にもしばらく気が付かなかった．