社区讨论

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 条回复,欢迎继续交流。

正在加载回复...