$$n\cdot a^n=b\; (mod\;p)$$

$$((p-1)q+r)\cdot a^r=b\; (mod\;p)$$

$$q=(b – r\cdot a^r)((p-1)\cdot a^r)^{-1}\; (mod\;p)$$

$$q=r-b\cdot a^{-r}\; (mod\;p)$$

$$(p-1)q’+r=(p-1)q+r\;(mod\; p)$$

$$q’=tp+q\quad \quad t\geq 0$$

$$x \geq n = (p-1)q’+r$$

$$\frac{x-r}{p-1} \geq q’$$

$$\frac{x-r}{p-1}-q \geq tp$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define Re register
#define pb push_back
#define F first
#define S second
#define ll long long
#define lowbit(x) (x & -x)
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 1000000007
#define N 50005
#define M 100005
ll a, b, p, x, ans, ar;
inline ll pow (ll x, ll y, ll mod)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
int main ()
{
scanf("%lld %lld %lld %lld", &a, &b, &p, &x);
ll up = p - 2;
fo (r, 0, up)
{
ar = pow(a, r, p);
ll q = (pow(ar * (p - 1) % p, p - 2, p) * (b - ar * r) % p + p) % p;
ll qmax = (x - r) / (p - 1);
if (x >= r && qmax >= q)
{
ans += (qmax - q) / p + 1;
if (!q && !r) --ans;
}
}
printf("%lld", ans);
}