akinyan's favorite numbers

#include <bits/stdc++.h>

using namespace std;

​

vector<pair<int, int>> bunkai(int x){

    vector<pair<int, int>> res;

    for(long long a = 2; a * a <= x; a++){

        if(x % a != 0){

            continue;

        }

        int e = 0;

        while(x % a == 0){

            e++;

            x /= a;

        }

        res.push_back({a, e});

    }

    if(x != 1){ 

        res.push_back({x, 1});

    }

    return res;

}

​

int main(){

    long long ans = 0;

    int n, x, y;

    cin >> n >> x >> y;

    vector<int> A(n);

    for(int i = 0; i < n; i++){

        cin >> A[i];

    }

    vector<pair<int, int>> X = bunkai(x), Y = bunkai(y);

    vector<vector<int>> P(X.size(), vector<int>(n + 1, 0)), Q(Y.size(), vector<int>(n + 1, 0));

    for(int i = 0; i < n; i++){

        for(int j = 0; j < X.size(); j++){

            int a = A[i];

            int e = 0;

            while(a % X[j].first == 0){

                e++;

                a /= X[j].first;

            }

            P[j][i + 1] = e + P[j][i];

        }

        for(int j = 0; j < Y.size(); j++){

            int a = A[i];

            int e = 0;

            while(a % Y[j].first == 0){

                e++;

                a /= Y[j].first;

            }

            Q[j][i + 1] = e + Q[j][i];

        }

    }

    for(int i = 0; i < n; i++){

        int okx = n, ngx = i - 1;

        while(okx - ngx > 1){

            int mid = (okx + ngx) / 2;

            bool flag = true;

            for(int j = 0; j < X.size(); j++){

                if(P[j][mid + 1] - P[j][i] < X[j].second){

                    flag = false;

                    break;

                }

            }

            if(flag) okx = mid;

            else ngx = mid;

        }

​

        int oky = n, ngy = i - 1;

        while(oky - ngy > 1){

            int mid = (oky + ngy) / 2;

            bool flag = true;

            for(int j = 0; j < Y.size(); j++){

                if(Q[j][mid + 1] - Q[j][i] < Y[j].second){

                    flag = false;

                    break;

                }

            }

            if(flag) oky = mid;

            else ngy = mid;

        }

​

        ans += abs(okx - oky);

    }

    cout << ans << endl;

}