#include "bits/stdc++.h" #include "atcoder/all" using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; using mint = modint998244353; const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; //const bool debug = false; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" #define P pair template inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } mint pm[100001][2][2]; mint pm2[100001][2][2]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long a, b, p, q; cin >> a >> b >> p >> q; if (0 == b) { // pre clac vectorpwa(100000 + 1), pwa2(100000 + 1); pwa[0] = 1; pwa2[0] = 1; mapmp; mp[0] = 0; mint memo = pow_mod(a, 100000, mod);//a^(10^5) rep(i, 100000) { pwa[i + 1] = pwa[i] * a; mp[pwa[i + 1].val()] = i + 1; pwa2[i + 1] = pwa2[i] * memo; } // x = 0, y = a // a^ n = p となる n // n = 10^5 * v + w; // v : fix rep(i, 100001) { mint aw = (mint)p * pwa2[i].inv(); if (mp.count(aw.val())) { long long ans = 100000LL * i + mp[aw.val()]; cout << ans << endl; return 0; } } } else { pm[0][0][0] = 1; pm[0][1][1] = 1; rep(i, 100000) { pm[i + 1][0][0] = pm[i][0][0] * a + pm[i][0][1]; pm[i + 1][0][1] = pm[i][0][0] * (-b); pm[i + 1][1][0] = pm[i][1][0] * a + pm[i][1][1]; pm[i + 1][1][1] = pm[i][1][0] * (-b); } mint ab = (mint)a * ((mint)b).inv(); mapmp; rep(i, 100001) { mint np = pm[i][0][0] * 2 + pm[i][0][1] * ab; mint nq = pm[i][1][0] * 2 + pm[i][1][1] * ab; mp[{np.val(), nq.val()}] = i; } pm2[0][0][0] = 1; pm2[0][1][1] = 1; mint s, t, u, v, invdet; invdet = pm[100000][0][0] * pm[100000][1][1] - pm[100000][0][1] * pm[100000][1][0]; invdet = invdet.inv(); s = pm[100000][1][1] * invdet; t = pm[100000][0][1] * -1 * invdet; u = pm[100000][1][0] * -1 * invdet; v = pm[100000][0][0] * invdet; rep(i, 100000) { pm2[i + 1][0][0] = pm2[i][0][0] * s + pm2[i][0][1] * u; pm2[i + 1][0][1] = pm2[i][0][0] * t + pm2[i][0][1] * v; pm2[i + 1][1][0] = pm2[i][1][0] * s + pm2[i][1][1] * u; pm2[i + 1][1][1] = pm2[i][1][0] * t + pm2[i][1][1] * v; } rep(i, 100001) { mint np = pm2[i][0][0] * p + pm2[i][0][1] * q; mint nq = pm2[i][1][0] * p + pm2[i][1][1] * q; if (mp.count({ np.val(),nq.val() })) { long long ans = 100000LL * i + mp[{ np.val(), nq.val() }]; cout << ans << endl; return 0; } } //debug /*rep(i, 4) { cout << pm[i][0][0].val() << " " << pm[i][0][1].val() << endl; cout << pm[i][0][1].val() << " " << pm[i][1][1].val() << endl; cout << endl; } cout << 2 << " " << ab.val() << endl;*/ } return 0; }