E-BirocratieInterstelara

#include <bits/stdc++.h>
#define MAXN 1717171
#define INF 1000000000000000000ll

using namespace std;

typedef long long ll;

ifstream fi("bir_interstelara.in");
ofstream fo("bir_interstelara.out");

ll n, a, b, MOD, inv_a, bucket;
ll Start[MAXN], rez, DP[MAXN], S1[MAXN], S2[MAXN];

ll inmult(ll a, ll b)
{
    if(a == 0) return 0;
    if(a % 2)
        return (b + 2 * inmult(a/2, b) % MOD) % MOD;
    return 2 * inmult(a/2, b) % MOD;
}

ll inversf(ll val) {
    val = (val - b + MOD) % MOD;
    val = inmult(val, inv_a) % MOD;
    return val;
}

ll expr(ll v, ll p)
{
    if(!p)return 1;
    if(p%2)
        return inmult(v, expr(inmult(v, v), p/2));
    return expr(inmult(v, v) % MOD, p/2);
}
unordered_map<ll, ll> Before;
ll a_compus, b_compus;

ll distanta(ll val)
{
    ll re = 0;
    if(Before.count(val))
        return Before[val];
    while(!Before.count(val)){
        val = (inmult(val, a_compus) + b_compus) % MOD; /// aplica functia de bucket ori
        re += bucket;
    }
    re += Before[val];
    return re;
}

ll inv(ll val)
{
    return expr(val, MOD-2);
}

void solve(ll R[])
{
    if(MOD <= 1000000) {
        for(int i = 0; i < MOD; ++i)
            DP[i] = INF;
        DP[0] = 0;
        ///varianta usoara
        ll x = 0, y = 0;
        do {
            y = inversf(x);
            DP[y] = DP[x] + 1;
            x = y;
        } while(y);
        DP[0] = 0;
        for(ll i = 1; i <= n; ++i)
            R[i] = DP[Start[i]];
    } else {
        ///cazul dificil
        ll x = 0;
        for(ll i = 0; i <= bucket + 2; ++i) {
            if(Before.count(x)) break;
            Before[x] = i;
            x = inversf(x);
        }

        a_compus = expr(a, bucket);
        b_compus = inmult((expr(a, bucket) -  1 + MOD) % MOD, inmult(inv(a-1), b));

        for(ll i = 1; i <= n; ++i)
            R[i] = distanta(Start[i]);
        Before.clear();
    }
}

int main()
{
    fi >> n >> a >> b >> MOD;
    bucket = (int)(sqrt(MOD) + .5);
    inv_a = expr(a, MOD-2);
    for(ll i = 1; i <= n; ++i)
        fi >> Start[i];
    solve(S1);
    b = (MOD - inmult(inv_a, b)) % MOD;
    swap(a, inv_a);
    solve(S2);

    for(int i = 1; i <= n; ++i)
        rez += min(S1[i], S2[i]);
    fo << rez << "\n";
    return 0;
}