首先观察到答案具有二分性,因此考虑二分答案。
对于check函数,朴素的想法就是枚举每个长度为mid的区间查询
我们发现区间gcd就等于区间最小值,因此考虑维护区间最小值和区间gcd
可以使用线段树维护,但是我们发现区间gcd也能使用st表维护
因此直接用st表维护这两个
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,pll> plll; const int N=5e5+10; const int inf=0x3f3f3f3f; const int mod=1e9+7; int a[N],f[N][30]; int g[N][30]; int lg[N],n; int gcd(int a,int b){ return b?gcd(b,a%b):a; } void init(){ int i,j; lg[1]=0; lg[2]=1; for(i=3;i<N;i++) lg[i]=lg[i>>1]+1; for(i=1;i<=n;i++){ f[i][0]=g[i][0]=a[i]; } for(j=1;j<=25;j++){ for(i=1;i+(1<<j)-1<=n;i++){ f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]); g[i][j]=gcd(g[i][j-1],g[i+(1<<j-1)][j-1]); } } } int MIN(int l,int r){ return min(f[l][lg[r-l+1]],f[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); } int GCD(int l,int r){ return gcd(g[l][lg[r-l+1]],g[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); } bool check(int mid){ int i; for(i=1;i+mid-1<=n;i++){ int j=i+mid-1; int x=MIN(i,j); int y=GCD(i,j); if(x==y) return true; } return false; } vector<int> num; int main(){ ios::sync_with_stdio(false); cin>>n; int i; for(i=1;i<=n;i++){ cin>>a[i]; } int j; init(); int l=1,r=n; while(l<r){ int mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } for(i=1;i+l-1<=n;i++){ int j=i+l-1; int x=MIN(i,j); int y=GCD(i,j); if(x==y) num.push_back(i); } cout<<(int)num.size()<<" "<<l-1<<endl; for(auto x:num){ cout<<x<<" "; } cout<<endl; return 0; }View Code