题目

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
 
const int N = 1e6 + 10;
const int mod = 998244353;
int a[N];
int st[N][22];
 
int get(int l, int r)
{
    int x = r - l + 1;
    int k = log2(x);
    return __gcd(st[l][k], st[r - (1 << k) + 1][k]); //第一个从l开始长度为k，第二个以r结尾，长度为k （允许重叠） 
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
 
    for (int i = 1; i <= n; i++)
        st[i][0] = a[i];
    for (int j = 1; 1 << j <= n; j++) //长度 
        for (int i = 1; i + (1 << j) - 1 <= n; i++) //尾巴 
        {
            st[i][j] = __gcd(st[i][j - 1], st[i + (1 << j-1)][j - 1]); //第二个保证是第一个尾巴的下一个（一般不重叠） 
        }
 
    LL ans = 0;
    for (int l = 1; l <= n; l++)
    {
        int r = l;
        int x = a[l];
 
        while (r <= n)
        {
            int ll = r;
            int rr = n;
 
            while (ll < rr)
            {
                int mid = ll + rr + 1 >> 1;
                if (get(l, mid) == x)
                    ll = mid;
                else
                    rr = mid - 1;
            }
            LL rsum;
            rsum = 1ll * (r + rr) * (rr - r + 1) / 2;
            ans = (ans + 1ll * l * rsum % mod * x % mod) % mod;
            r = rr + 1;
            if (r <= n)
                x = __gcd(x, a[r]);
        }
    }
 
    printf("%lld\n", ans);
}