社区讨论
WA求助
P7009 [CERC2013] Magical GCD参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhj98ngv
- 此快照首次捕获于
- 2025/11/03 22:48 4 个月前
- 此快照最后确认于
- 2025/11/03 22:48 4 个月前
错误位置:
CPP
Wrong Answer.wrong answer On line 3847 column 2, read 4, expected 2.
代码:
CPP#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1.2e5;
int n,m;
int a[N];
int loge[N],st[N][31];
int gcd(int a,int b){
if(b==0){
return a;
}
return gcd(b,a%b);
}
void _init(){
for(int i=2;i<=n;i++){
loge[i]=loge[i>>1]+1;
}
for(int i=0;i<N;i++){
st[i][0]=0;
}
for(int i=1;i<=n;i++){
st[i][0]=a[i];
}
for(int i=1;i<=27;i++){
for(int j=1;j<=n-(1<<i)+1;j++){
st[j][i]=gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int find(int x,int y){
int l=loge[y-x+1];
return min(st[x][l],st[y-(1<<l)+1][l]);
}
signed main(){
int T;
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
_init();
int maxx=0;
for(int i=1;i<=n;i++){
for(int ll=i;ll<=n;){
int l=ll,r=n;
while(l+1<r){
int mid=(l+r)/2;
if(find(i,mid)==find(i,ll)){
l=mid;
}else{
r=mid-1;
}
}
int top;
if(find(i,r)==find(i,ll)){
top=r;
}else{
top=l;
}
maxx=max(maxx,find(i,ll)*(top-i+1));
ll=top+1;
}
}
printf("%lld\n",maxx);
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...