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
なんでこれで上手く行くのかについて説明します。
ここでやりたいのは更新式
mod
をc回行ったら最初のの値に応じて最終的なの値はどうなるか?ということを求めたいです(更新式は上に貼った解説のページの変数ではなく問題文にあるような変数の定義の仕方をしています)。これを求めるために,「定数項の部分」と「初期値()に依存する部分」に分けて値を求めてみます。
定数項の部分はよく考えると,毎回今までの定数項の部分を倍してその後だけ足す,ということを繰り返しているだけです。なので,上の式で言うとQを計算し続けるだけで定数項の部分を求めることが出来ます。
次に,「初期値に依存する部分」です。こちらは,次のように考えています。「仮に,初期値が1だとして計算してみる。上記の更新式は線形なので1の場合がわかれば一般のxについてはx倍するだけで初期値を求められる。」
ということで,初期値が1の場合を考えてみると,これは毎回倍するだけなので上の式の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; }