题解归档 - cf104118L

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118L
• 本地来源：problems/cf104118L/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/L
• 原始标题：Gym 104118L - LCG Manipulation

思路

Gym 104118L - LCG Manipulation

For x_n = a x_{n-1} + b (mod p), with prime p.

Cases:

• If s == v, answer is 0.
• If a == 1, then x_n = s + n b, so solve one modular linear equation.
• Otherwise, shift by the fixed point c = b / (1-a).

Then:

x_n - c = a^n (s - c).

If s = c, the sequence is constant. Otherwise solve:

a^n = (v-c)/(s-c) (mod p).

This is a discrete logarithm in F_p^*, handled by baby-step giant-step in O(sqrt(p)).

Checks:

• official sample 1
• random small-prime brute force against direct simulation

代码

来源：problems/cf104118L/solution.cpp

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

ll mod_pow(ll a, ll e, ll mod) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return r;
}

ll inv_mod(ll x, ll p) {
    return mod_pow((x % p + p) % p, p - 2, p);
}

ll discrete_log(ll a, ll target, ll p) {
    a %= p;
    target %= p;
    if (target == 1) return 0;

    ll order = p - 1;
    int m = (int)ceil(sqrt((long double)order));

    unordered_map<int, int> baby;
    baby.reserve((size_t)m * 2);
    baby.max_load_factor(0.7);

    ll cur = 1;
    for (int j = 0; j < m; ++j) {
        if (!baby.count((int)cur)) baby[(int)cur] = j;
        cur = cur * a % p;
    }

    ll am = mod_pow(a, m, p);
    ll step = inv_mod(am, p);
    cur = target;
    for (int i = 0; i <= m; ++i) {
        auto it = baby.find((int)cur);
        if (it != baby.end()) {
            ll ans = 1LL * i * m + it->second;
            if (ans < order) return ans;
        }
        cur = cur * step % p;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        ll a, b, s, p, v;
        cin >> a >> b >> s >> p >> v;

        if (s == v) {
            cout << 0 << '\n';
            continue;
        }

        if (a == 1) {
            ll ans = (v - s + p) % p * inv_mod(b, p) % p;
            cout << ans << '\n';
            continue;
        }

        // Fixed point c satisfies c = a*c + b (mod p).
        ll c = b * inv_mod(1 - a, p) % p;
        if (s == c) {
            cout << "IMPOSSIBLE\n";
            continue;
        }

        ll lhs = (v - c + p) % p;
        if (lhs == 0) {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        ll rhs = lhs * inv_mod((s - c + p) % p, p) % p;
        ll ans = discrete_log(a, rhs, p);
        if (ans < 0) cout << "IMPOSSIBLE\n";
        else cout << ans << '\n';
    }
    return 0;
}