ST表

在维护静态的区间最大值或者区间最大公因数时，我们常常会用到$ST $表来存储对应的属性

思路：倍增，每次把区间长度扩大两倍

题目

HERE!

有$n$名同学，他们的开心值为$a[0],a[1]…a[n−1]$。现在从中随机选取一个区间的同学进行聚会。对于一个区间$[l,r](l<=r)$的同学，大家在一块聚会后，每个人的开心值就会同时变为$gcd(a[l],a[l+1]…a[r])$，本次的聚会的开心值即为所有参加聚会的同学的开心值之和。请你求出这次聚会的开心值的期望，并$mod $ $998244353$输出。

输入描述

第一行输入一个整数 $n$ ,$1 \leq n\leq 2\times1e5$，表示同学总数。

第二行输入 $n$ 个整数 $( a_0, a_1, a_2, \ldots, a_{n-1} )$，表示 $n$ 名同学的各自的开心值$( 1 \leq a_i \leq 2 \times 10^5 )$

输出描述

输出一个整数 $ ans $，表示这次聚会的开心值的期望。可以证明，答案总是一个有理数。将其化为不可约分数 $ \frac{p}{q} $ 后，在区间 $ [0, 998244353) $ 中存在唯一整数 $ ans $ 满足 $ ans \times q \equiv p $，输出 $ ans $​。

思路

• 关于$ST$表的使用，因为$gcd$是可以重叠的区间属性，所以我们想到用$ST$ 表来加速对区间 $gcd$的计算
• Q: 为什么可行？要是区间有很多段不同的$gcd$​ ，那不是得爆掉？-----这就得考虑一段区间 $gcd$ 的性质，假设有两段相邻的区间的最大公因数分别是 $gcd1$和 $gcd2$ 如果两者相等，那么合并之后 $gcd$ 大小不变，如果二者不相等，我们假设 $gcd1<gcd2$ 那么$gcd2$肯定会有多的一个因子，并且这个因子最小是2，所以$gcd$ 会至少变为$gcd2/2$，所以我么一段区间最多只会有 20段$(log_2{2e5})$

#pragma GCC optimize(2)
#include <algorithm>
#include <cstring>
#include <iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define lowbit(x) x & -x
#define int long long
#define pii pair<int ,int >
#define  fi first
#define se second
const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod =998244353;
int st[N][20];//st[i][j]表示i为起点，区间长度为2^j的gcd为多少
int a[N];
int LOG[N];
int query(int l,int r)
{
    int k=LOG[r-l+1];
    return __gcd(st[l][k],st[r-(1<<k)+1][k]);
}
int qpow(int a,int b)
{
    a%=mod;
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
// 1 2 3 4 5 ... n
// st[i][j] 从第i个数开始，到第i+2^(j)-1个数的gcd 
// 怎么去询问[l,r] ？
//  2^(k+1) > len([l,r]) >= 2^k  
// [l,l+2^k-1],[r-2^k+1,r]
void solve() {
    int n;
    cin>>n;
    LOG[0]=-1;
    for(int i=1;i<N;i++)
    {
        LOG[i]=LOG[i>>1]+1;
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) st[i][0]=a[i];
    for(int j=1;j<=20;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]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int R=i;
        while(R<=n)
        {
            int l=R,r=n;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(query(i,R)==query(i,mid)) l=mid;
                else r=mid-1;
            }
                //关于区间最大公因数的性质
                //  2e5 >= gcd(a[l],a[l+1],...,a[r]) = X 
                // 不相等 
                // gcd(a[l],a[l+1],...,a[r],a[r+1]) <= X/2 
                // l = 1
                // [1,1] , [1,2] ,...,[1,n] 20种情况 
            ans=(ans+(r-R+1)*(R+r-2*i+2)/2%mod*query(i,R))%mod;
            R=r+1;

        }
    }
    // cout<<ans<<'\n';
    int inv=n*(n+1)/2%mod;
    inv=qpow(inv,mod-2);
    cout<<ans*inv%mod;

}



/*


*/


#undef int
int main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cout<<fixed<<setprecision(15);


  // int _ = 1;cin >>_;while(_--)
  {
    solve();
  }
  return 0;
}