分析

我们换一个题面，其实是要我们求 。那么我们发现这个 的出现太突兀了，考虑用枚举这个 。那么我们枚举 之后，就暴力枚举这个区间就可以了。为什么呢？我们可以证明 只会有 种取值。那么我们完全可以再枚举一个 ，又因为 的大小是具有单调性的，所以二分枚举边界就可以了。关键是 的枚举，我们可以采用笛卡尔树来做，也可以使用 的 的建树。这里才用了单调栈的 建树，总的复杂度为 。轻松最优解。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 2e5 + 1000,mod = 1e9 + 7;
int A[N],top,rc[N],lc[N],st[N],n,Ans = 0;
int L[N],siL[N],R[N],siR[N],S[21][N],Log[N];
int gcd(int a,int b) {return b ? gcd(b,a % b) : a;}
int get(int l,int r) {
    int k = Log[r - l + 1];
    return gcd(S[k][l],S[k][r - (1 << k) + 1]);
}
void solve(int u,int l,int r) {
    if(lc[u]) solve(lc[u],l,u-1);if(rc[u]) solve(rc[u],u+1,r);
    int x = u,y = u;L[0] = 0;R[0] = 0;siL[0] = 0;siR[0] = 0;
    while(l <= x) {
        L[++L[0]] = get(x,u);
        int ll = l,rr = x,ans = x;
        while(ll <= rr) {
            int mid = ll + rr >> 1;
            if(get(mid,u) == L[L[0]]) rr = mid - 1,ans = min(ans,mid);
            else ll = mid + 1;
        }
        siL[++siL[0]] = x - ans + 1;x = ans - 1;
    }
    while(y <= r) {
        R[++R[0]] = get(u,y);
        int ll = y,rr = r,ans = y;
        while(ll <= rr) {
            int mid = ll + rr >> 1;
            if(get(u,mid) == R[R[0]]) ll = mid + 1,ans = max(ans,mid);
            else rr = mid - 1;
        }
        siR[++siR[0]] = ans - y + 1;y = ans + 1;
    }
    int res = 0;
    for(int i = 1;i <= L[0];i++) {
        for(int j = 1;j <= R[0];j++) {
            int tot = gcd(L[i],R[j]);
            res = (res + 1LL * tot * siL[i] % mod * siR[j] % mod) % mod;
        }
    }
    Ans = (Ans + 1LL * res * A[u] % mod) % mod;
}
signed main() {
    n = read();
    for(int i = 1;i <= n;i++) A[i] = read(),S[0][i] = A[i];
    for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1;i <= n;i++) {
        int k = top;
        while(k && A[st[k]] < A[i]) k--;
        if(k) rc[st[k]] = i;
        if(k < top) lc[i] = st[k + 1];
        st[++k] = i;top = k;
    }
    for(int i = 1;i <= 19;i++) {
        for(int j = 1;j + (1 << i) - 1 <= n;j++) {
            S[i][j] = gcd(S[i-1][j],S[i-1][j + (1 << i - 1)]);
        }
    }
    solve(st[1],1,n);
    cout << Ans << endl;
    return 0;
}