即求删掉一个子序列的gcd之和。注意到前后缀gcd的变化次数都是log级的，于是暴力枚举前缀gcd和后缀gcd即可。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 #define P 998244353 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,a[N],prepos[N],prenum[N],precnt,sufpos[N],sufnum[N],sufcnt,ans; int main() { #ifndef ONLINE_JUDGE freopen("bzoj4921.in","r",stdin); freopen("bzoj4921.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); prepos[0]=0; for (int i=1;i<=n;i++) if (gcd(a[i],prenum[precnt])!=prenum[precnt]) precnt++,prepos[precnt]=i,prenum[precnt]=gcd(a[i],prenum[precnt-1]); prepos[precnt+1]=n+1; sufpos[0]=n+1; for (int i=n;i>=1;i--) if (gcd(a[i],sufnum[sufcnt])!=sufnum[sufcnt]) sufcnt++,sufpos[sufcnt]=i,sufnum[sufcnt]=gcd(a[i],sufnum[sufcnt-1]); sufpos[sufcnt+1]=0; for (int i=0;i<=precnt;i++) for (int j=0;j<=sufcnt;j++) { int x=gcd(prenum[i],sufnum[j]); for (int k=prepos[i];k<prepos[i+1];k++) ans=(ans+1ll*x*max(0,sufpos[j]-max(sufpos[j+1],k+1))%P)%P; } ans-=a[1],ans-=a[n];while (ans<0) ans+=P; cout<<ans; return 0; }