一个非常众所周知的结论，一个序列的前缀\(\gcd\)只会有\(\log\)种取值

于是考虑一下一些暴力的东西，我们枚举每个点作为左端点，二分出前缀\(\gcd\)变化的位置，复杂度大概是\(\operatorname{O(nlog^3n)}\)，好像非常垃圾的样子

我们考虑直接从后往前枚举左端点，每次往前加入一个数，和之前的前缀\(\gcd\)再取一个\(\gcd\)就好了，同时合并掉相同的一段

复杂度是\(\operatorname{O(nlog^2n)}\)，还是挺丢人的

代码

#include
    
     #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline LL read() {    char c=getchar();LL x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3ll)+(x<<1ll)+c-48,c=getchar();return x;}const int maxn=1e5+5;LL gcd(LL a,LL b) {return !b?a:gcd(b,a%b);}LL a[maxn];int n;LL ans;LL b[maxn],c[maxn];int p[maxn],top,t[maxn];int main() {    n=read();    for(re int i=1;i<=n;i++) a[i]=read();    ans=a[n];b[++top]=ans;p[1]=n;    for(re int i=n-1;i;--i) {        for(re int j=top;j;--j)            b[j]=gcd(b[j],a[i]);        b[++top]=a[i];p[top]=i;        int tot=0;        for(re int j=top-1;j>=0;--j) {            if(b[j]==b[j+1]) continue;            c[++tot]=b[j+1],t[tot]=p[j+1];        }        top=tot;        for(re int j=top;j;--j)             b[j]=c[top-j+1],p[j]=t[top-j+1],ans=max(ans,1ll*b[j]*(p[j]-i+1));    }    printf("%lld\n",ans);    return 0;}