@[Ivan422](/user/662425) P7009限时8s
by TC_QD @ 2024-04-18 18:47:01
@[wangyuezhang](/user/1335720) 但是我数据点只跑了2s
by Ivan422 @ 2024-04-18 19:07:43
因为常数不够优秀。
另外，时间复杂度显然不是 $O(tn\log n)$，因为有 $\gcd$。
改了一下代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,M=25;
int n,m,a[N],LOG[N],st[N][M],ans; //数组改小了
int ggcd(int x,int y){
int c=x%y;
while(y!=0){c=x%y;x=y;y=c;}
return x;
}
int st_q(int l,int r){
int k=LOG[r-l+1];
int gcd=__gcd(st[l][k],st[r-(1<<k)+1][k]);//用 STL 的 __gcd，虽然貌似没啥用（？）
return gcd;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)st[i][0]=a[i];
for(int k=1;k<=LOG[n];k++){
int len=1<<k;
for(int i=1;i<=n-len+1;i++){
st[i][k]=__gcd(st[i][k-1],st[i+(1<<k-1)][k-1]);//用 STL 的 __gcd，虽然貌似没啥用（？）
}
}
ans=0;
for(int i=1;i<=n;i++){
int x=i;
while(x<=n){
int l=x,r=n+1,mid,tmp = st_q(i,x);//提前存下 st_q(i,x)
while(l+1<r){
mid=(l+r)/2;
if(st_q(i,mid)==tmp)l=mid;
else r=mid;
}
ans=max(ans,tmp*(l-i+1));
x=l+1;
}
}
cout<<ans<<endl;
return;
}
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//关闭同步流
LOG[0]=-1;
for(int i=1;i<N;i++)LOG[i]=LOG[i>>1]+1;//这里要改成 <N，虽然对常数没有影响，但是当 i=N 是会出现数组越界，属于 UB
int t;cin>>t;
while(t--)solve();
return 0;
}
```
by linxuanrui @ 2024-04-18 19:11:16
@[Ivan422](/user/662425)
by linxuanrui @ 2024-04-18 19:11:45
@[linxuanrui](/user/857323)
感谢！
by Ivan422 @ 2024-04-18 19:12:27
@[linxuanrui](/user/857323)
卡常？
by Ivan422 @ 2024-04-18 19:17:32