• Trước hết, ta cần nhận xét 1 tính chất quan trọng của ~x~: ~x~ phải là phần tử có giá trị nhỏ nhất trong đoạn "có thể tối giản".

• Một hướng đi có thể nghĩ đến trong bài này là với mỗi ~a_i~, nó sẽ đóng vai trò là phần tử ~x~ trong bao nhiêu đoạn con. ~a_i~ phải là phần tử nhỏ nhất và duy nhất (1), đồng thời mọi phần tử trong đoạn phải chia hết cho ~a_i~, hay ~UCLN~ của đoạn bằng ~a_i~ (2).**

• Với (1), ta có thể sử dụng stack đơn điệu để tìm khoảng ~[L, R]~ thỏa mãn ~a_i~ nhỏ nhất và duy nhất.

• Với (2), sau khi tìm được đoạn ~[L, R]~ thỏa mãn (1), ta cần thu hẹp lại đoạn thành ~[L', R']~ ~(L \le L', R \ge R')~ để ~gcd(a_L, a_{L+1}, ..., a_R') = a_i~. Ở bước này, ta có thể sử dụng chặt nhị phân 2 lần để tìm ~L'~ và ~R'~. Với mỗi lần sử dụng hàm ~check~ trong chặt nhị phân, ta cần biết được ~gcd(a_{mid}, a_{mid+1}, ..., a_i)~ hoặc ~gcd(a_i, a_{i+1}, ..., a_{mid})~ là bao nhiêu. Bước này có thể sử dụng Segment Tree, tuy nhiên với độ phức tạp ~O((logn)^2)~ với mỗi lần truy vấn, độ phức tạp cuối cùng lên tới ~O(n(logn)^3)~ có thể bị TLE. Để khắc phục, ta cần cải tiến sử dụng ~Sparse~ ~Table~ với độ phức tạp mỗi truy vấn chỉ là ~O(logn)~, với tổng độ phức tạp ~O(n(logn)^2)~**

Code mẫu

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second

using namespace std;
const int MAXN = 3e5 + 5;
const int LOG = 17;
int n, a[MAXN], l[MAXN], r[MAXN];
int gcd[MAXN][LOG + 2];
void prep(){
    stack<int> L, R;
    for (int i = 1; i <= n; i++){
        while (L.size() && a[L.top()] > a[i]) L.pop();
        l[i] = L.size() ? L.top() + 1 : 1;
        L.push(i);
    }
    for (int i = n; i >= 1; i--){
        while (R.size() && a[R.top()] > a[i]) R.pop();
        r[i] = R.size() ? R.top() - 1 : n;
        R.push(i);
    }
}
void buildRMQ(){
    for (int i = 1; i <= n; i++) gcd[i][0] = a[i];
    for (int k = 1; (1 << k) <= n; k++){
        for (int i = 1; i + (1 << k) <= n + 1; i++){
            gcd[i][k] = __gcd(gcd[i][k - 1], gcd[i + (1 << (k - 1))][k - 1]);
        }
    }
}
int getGCD(int l, int r){
    int log = log2(r - l + 1);
    return __gcd(gcd[l][log], gcd[r - (1 << log) + 1][log]);
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    prep();
    buildRMQ();
    int ans = 0;
    for (int i = 1; i <= n; i++){
        int fl = i, fr = i;
        int le = l[i], ri = i;
        while (le <= ri){
            int mid = (le + ri) >> 1;
            if (getGCD(mid, i) == a[i]) fl = mid, ri = mid - 1;
            else le = mid + 1;
        }
        le = i, ri = r[i];
        while (le <= ri){
            int mid = (le + ri) >> 1;
            if (getGCD(i, mid) == a[i]) fr = mid, le = mid + 1;
            else ri = mid - 1;
        }
        ans += (fr - i + 1) * (i - fl + 1) - 1;
    }
    cout << ans; 
}