Xét một số ~k~ bất kì. Ta có ~x^2-1 = x(x+1) + (x - 1) - 2x~. Ta thấy:

• ~x(x+1)~ tương ứng với số subarray ~[l,r]~ thoả mãn ~\gcd(a_i, k)=1 \ \forall i \in [l,r]~
• ~x-1~ tương ứng với số subarray thoả mãn, và có độ dài ~2~
• ~x~ tương ứng với số subarray thoả mãn, và có độ dài ~1~

Từ đó ta nghĩ đến việc tính contribution của từng subarray vào kết quả. Xét một subarray ~[l,r]~, ta cần đếm số số ~k \in [1,V]~ mà ~\gcd(a_i, k)=1 \ \forall i \in [l,r]~. Điều này tương đương với ~\gcd(k, \text{lcm}(a_l, \ldots, a_r)) = 1~.

• Subtask 1:
  • Ta duyệt mọi subarray ~[l,r]~
  • Với mỗi subarray, gọi ~p_1, \ldots, p_m~ là tập hợp các số là ước nguyên tố của ít nhất một số trong đoạn ~[l,r]~.
  • Nhận thấy ~m \le 10~ do ~a_i \le 30~. Do đó ta có thể bao hàm loại trừ để tính số số ~\gcd(k, \text{lcm}(a_l, \ldots, a_r)) = 1~ với ~1 \le k \le V~ trong ~2^m~. Như vậy độ phức tạp là ~O(n^2 \cdot 2^{10})~ (lưu ý kĩ thuật duyệt mask để độ phức tạp không bị nhân thêm ~10~).
• Subtask 2:
  • Vẫn duyệt ~[l,r]~ giống như subtask 1, nhưng nhận thấy với mỗi ~l~, mảng ~p~ chỉ thay đổi tối đa ~10~ lần khi duyệt ~r~ tăng dần.
  • Như vậy với mỗi ~l~, ta chặt nhị phân để tìm ra ~10~ điểm ~r~ làm thay đổi mảng ~p~. Với mỗi điểm làm thay đổi mảng ~p~, ta bao hàm loại trừ để tính số số ~\le V~ và nguyên tố cùng nhau với mọi số trong tập ~p~. Trường hợp tệ nhất là với mỗi ~n~, ta phải bao hàm loại trừ lại ~10~ lần, nghĩa là mất ~2^1 +2^2 + \cdots +2^{10} \approx 2046~ phép tính. Vậy độ phức tạp là ~O(2046n)~
• Subtask 3:
  • Chỉ có ~10~ số nguyên tố ~\rightarrow~ ta có thể tính trước kết quả bao hàm loại trừ cho ~2^{10}~ tập các ước nguyên tố có thể, mất ~2^{20}~ phép tính
  • Kết hợp với nhận xét ở subtask 2, ta giảm độ phức tạp còn ~O(10n + 2^{20})~
• Subtask 4:
  • Từ các subtask trước, ta rút ra được công thức tính số số nguyên tố cùng nhau với một tập ~\{p_1, p_2, \ldots, p_m\}~ là ~V(\frac{p_1-1}{p_1}) \ldots (\frac{p_m-1}{p_m})~. Và theo input thì ~V~ luôn chia hết cho mọi số nguyên tố từ ~2~ đến ~10^6~, nên phép mod không làm ảnh hưởng đến kết quả của bài toán trên
  • Vậy với subtask này, ta có thể duyệt đoạn ~[l,r]~; lọc ra các ước nguyên tố; và tính contribution vào kết quả. Độ phức tạp ~O(n^3)~
• Subtask 5:
  • Khi duyệt cố định ~l~, mỗi lần tịnh tiến ~r~ ta chỉ cần nhân thêm các ước nguyên tố mới xuất hiện tại ~r~. Độ phức tạp giảm còn ~O(n^2)~
• Subtask 6:
  • Sử dụng segment tree, với mỗi ~r~ ta lưu ~f_l~ là đáp án cho đoạn ~[l,r]~
  • Duyệt ~r~ tăng dần. Gọi các ước nguyên tố của ~a_r~ là ~\{p_1, p_2, \ldots, p_m\}~. Với mỗi ước ~p_i~, ta nhân ~f[last[p_i]+1 \ldots i]~ thêm một lượng ~\frac{p_i-1}{p_i}~, với ~last[x]~ là vị trí gần ~r~ nhất mà xuất hiện ước nguyên tố ~x~.
  • Vậy bài toán quy về cập nhật nhân một đoạn và truy vấn tổng. Đây là ứng dụng cơ bản của segment tree với lazy update.
  • Độ phức tạp: ~O(n \log n \log (\max A))~

#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 42
#endif

const int MOD = 1e9 + 7;
const int MX = 1e6+5;

int add(int a, int b) {
    if ((a += b) >= MOD) a-=MOD;
    return a;
}

int mul(int a, int b) {
    return 1LL * a * b % MOD;
}

int modpow(int a, long long p) {
    int res = 1;
    for (; p > 0; p >>= 1, a = mul(a,a))
        if (p & 1) res = mul(res, a);
    return res;
}

int inv(int a) {
    return modpow(a, MOD-2);
}

int num_V = 1;

struct LazySeg {
    int n;
    vector<int> seg;
    vector<int> lazy;

    void init(int _N) {
        n = _N;
        seg.assign(n*4 + 7, 0);
        lazy.assign(n*4 + 7, 1);
    }

    void build(int ind, int L, int R) {
        if (L == R) seg[ind] = num_V;
        else {
            int mid = L + R >> 1;
            build(ind << 1, L, mid);
            build(ind << 1 | 1, mid + 1, R);
            seg[ind] = add(seg[ind << 1], seg[ind << 1 | 1]);
        }
    }

    void push(int ind) {
        if (lazy[ind] != 1) {
            for (int i = 0; i < 2; i++) {
                seg[ind<<1|i] = mul(seg[ind<<1|i], lazy[ind]);
                lazy[ind<<1|i] = mul(lazy[ind<<1|i], lazy[ind]);
            }
            lazy[ind] = 1;
        }
    }

    void upd(int l, int r, int val, int ind, int L, int R) {
        if (l > R || r < L) return;
        if (l <= L && R <= r) {
            lazy[ind] = mul(lazy[ind], val);
            seg[ind] = mul(seg[ind], val);
            return;
        }
        push(ind);
        int mid = L + R >> 1;
        upd(l, r, val, ind << 1, L, mid);
        upd(l, r, val, ind << 1 | 1, mid + 1, R);
        seg[ind] = add(seg[ind << 1], seg[ind << 1 | 1]);
    }

    void upd(int l, int r, int val) {
        upd(l, r, val, 1, 1, n);
    }

    int query(int l, int r, int ind, int L, int R) {
        if (l > R || r < L) return 0;
        if (l <= L && R <= r) return seg[ind];
        push(ind);
        int mid  = L + R >> 1;
        return add(query(l, r, ind << 1, L, mid),
                    query(l, r, ind << 1 | 1, mid + 1, R));
    }

    int query(int l, int r) {
        return query(l, r, 1, 1, n);
    }
};

bool isPrime[MX];
vector<int> prime_factors[MX];

int n;
int a[MX];
int pw[MX];
int last_occur[MX];
int f[MX];
int seed, mul_num, add_num, mod;

LazySeg seg;

void solve() {
    memset(isPrime, true, sizeof isPrime);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < MX; i++) {
        if (isPrime[i]) {
            for (int j = i; j < MX; j += i) {
                isPrime[j] = false;
                prime_factors[j].push_back(i);
            }
        }
    }

    cin >> n;

    cin >> seed >> mul_num >> add_num >> mod;
    for (int i = 1; i <= 1000000; i++) {
        if (i == 1) {
            f[i] = seed;
        }
        else {
            f[i] = (1LL * f[i-1] * mul_num + add_num)%mod + 1;
        }
        num_V = mul(num_V, modpow(i, f[i]));
    }

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }


    seg.init(n);
    seg.build(1, 1, n);
    int ans = 0;

    for (int r = 1; r <= n; r++) {
        for (const auto &p : prime_factors[a[r]]) {
            int prime_contribution = mul(p - 1, inv(p));
            seg.upd(last_occur[p] + 1, r, prime_contribution);
            last_occur[p] = r;
        }

        ans = add(ans, mul(2, seg.query(1, r)));
        ans = add(ans, seg.query(r - 1, r - 1));
        ans = add(ans, MOD - mul(2, seg.query(r, r)));
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;
    // cin >> tt;
    for(int i = 1; i <= tt; i++) {
        // cout << "Case " << i << "#: ";
        solve();
    }

    return 0;
}