L - LCG Manipulation

Code

#include <bits/stdc++.h>
//#define int long long
#define ll long long
using namespace std;
const ll N = (1ll<<31)-1;
const ll m = 46345;
const ll INF = 1e16+1;

ll a,b,v,s,p;
ll pw(ll a, int b) {
    if (b == 0) return 1;
    ll tmp = pw(a, b/2)%p;
    tmp *= tmp;
    tmp %= p;
    if (b&1) return (tmp*(a%p))%p;
    return tmp;
}
void solCase1() {
    // min n which s + bn = v <=> bn = v-s
    if (v - s < 0) cout << "IMPOSSIBLE";
    else {
        if ((v-s)%b != 0) cout << "IMPOSSIBLE";
        else cout << ((v-s)*pw(b, p-2))%p;
    }
    return;
}
void sol() {
    cin >> a >> b >> s >> p >> v;
    if (a == 1) {
        solCase1();
    }
    else {
        ll M = b%p + (v*(a-1))%p;
        M %= p;
        ll tmp = s*(a-1); tmp %= p;
        tmp += b; tmp %= p;
        M *= pw(tmp, p-2); M %= p;
//        tim a^n == M
//        a^(m*i + j) == M
//        (a^m)^i * a^j == M
//        a^m^i == M / a^j
        map<ll, int> minVal;
        for (ll j=0, aj=1;j <= m;j++) {
            ll x = M * pw(aj, p-2);
            x %= p;
            if (minVal.count(x) == 0)
                minVal[x] = j;
            aj *= a; aj %= p;
        }
        ll ans = INF;
        for (ll i=0, am=pw(a, m), vt = 1;i <= m;i++) {
            if (minVal.count(vt))
                ans = min(ans, i*m+minVal[vt]);
            vt *= am;
            vt %= p;
        }
        if (ans == INF)
            cout << "IMPOSSIBLE";
        else
            cout << ans;
    }
}
signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int t; cin >> t;
    while(t--) {
        sol();
        cout << endl;
    }

    return 0;
}