#include <bits/stdc++.h>   using namespace std;   long long pow1(long long b, long long expo, long long md) {     if (!expo) return 1;     long long tmp = pow1(b, expo / 2, md);     tmp = (tmp * tmp) % md;     if (expo % 2) tmp = (tmp * b) % md;     return tmp;   }   long long w[1000005] = {};   long long apow[1000005] = {};   long long inv[1000005] = {};   vector<long long> v[1000005] = {};   long long get(long long a, long long m1, long long b, long long m2,                 long long x) {     long long ret = 0;     long long first, k;     k = (a - b) * inv[m2];     k %= m1;     k += m1;     k %= m1;     first = k * m2 + b;     first %= m1 * m2;     x -= first;     if (x >= 0) {       ret += 1 + x / (m1 * m2);     }     return ret;   }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     cout << fixed << setprecision(15);     long long md, a, b, x, per;     long long ans = 0;     cin >> a >> b >> md >> x;     apow[0] = 1;     v[1].push_back(0);     if (a != 1) {       apow[1] = a;       v[a].push_back(1);       for (long long f = (long long)2; f <= (long long)md; ++f) {         apow[f] = a * apow[f - 1];         apow[f] %= md;         if (apow[f] == 1) {           per = f;           break;         }         v[apow[f]].push_back(f);       }     } else {       per = 1;     }     for (long long f = (long long)1; f <= (long long)md - 1; ++f) {       inv[f] = pow1(f, md - 2, md);     }     for (long long f = (long long)1; f <= (long long)md - 1; ++f) {       w[f] = (inv[f] * b) % md;     }     for (long long f = (long long)1; f <= (long long)md - 1; ++f) {       if ((long)v[w[f]].size()) {         for (long long ff = (long long)0;              ff <= (long long)(long)v[w[f]].size() - 1; ++ff) {           ans += get(f, md, v[w[f]][ff], per, x);         }       }     }     cout << ans;     return 0;   }   