题解

直接使用ST表秒周杀!!!

呆码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gd[100100]={},st[101][100100]={},bs[100100]={},lg[100100]={},n;
ll maxn=0;
void logInit(){
	for(ll i=2;i<100100;i++){
		lg[i]=lg[i>>1]+1;
	}
}
void stInit(){
	//O(n log n)
	for(ll i=1;i<=lg[n];i++){
		for(ll j=1;j<=n-(1<<i)+1;j++){
			st[i][j]=__gcd(st[i-1][j],st[i-1][j+(1<<(i-1))]);
		}
	}
}
ll question(ll l,ll r){
	ll k=lg[r-l+1];
	return __gcd(st[k][l],st[k][r-(1<<k)+1]);
}
ll ck(ll ls,ll l,ll c){
	ll r=n;
	while(l<r){
		ll mid=(l+r+1)>>1;
		if(question(ls,mid)==c)l=mid;
		else r=mid-1;
	}
	return l;
}
int main(){
	ll T;
	scanf("%lld",&T);
	logInit();
	while(T--){
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
			scanf("%lld",&st[0][i]);
		stInit();
		maxn=0;
		for(ll i=1;i<=n;i++){
			for(ll lp=i,tem=0;lp<=n;lp=tem+1){
				ll jz=question(i,lp);
//				cout<<jz<<" "<<ck(lp,jz)<<" "<<i<<" "<<lp<<" ";
				tem=ck(i,lp,jz);
				maxn=max(maxn,(tem-i+1)*jz);
//				cout<<tem<<endl;
			}
		}
		printf("%lld\n",maxn);
	}
	return 0;
}

Q：为什么看起来这么简单，调了这么久？？？
A：调半天愣是没发现数组开错了，st数组开成st[100100][101]了......
蚘疐鶗刼，崥汿阽饡!!!