题解 CF359D 【Pair of Numbers】

ChthollyTree

2019-03-29 16:25:51

Solution

因为一个区间满足条件 设为[l,r] “满足区间中有一个数 x 可以整除区间中任意数” 则[l,r] 的所有包含 x 的子区间 [l',r'] 必然也满足条件 所以区间长度就具有单调性,就可以二分 至于判定一个区间是否符合条件,可以用线段树 每个节点维护区间gcd 同时这个区间的x一定是区间的最小值 可以rmq求 最后判定区间gcd是不是x的倍数就可以了 (当然直接判定线段树上每个节点的区间gcd是不是x的倍数就行) ``` #include<bits/stdc++.h> using namespace std; #define MAXN 300005 #define INF 0x3f3f3f3f #define lc(i) (i<<1) #define rc(i) ((i<<1)|1) int n,m; int a[MAXN]; int f[MAXN][22]; struct aa { int l,r,s,a; }c[MAXN<<2]; int gcd(int x,int y) { if(x%y == 0) return y; return gcd(y,x%y); } void jianshu(int i,int l,int r) { int mid = (l+r)>>1; c[i].l = l; c[i].r = r; if(l == r) { c[i].s = a[l]; c[i].a = a[l]; return; } jianshu(lc(i),l,mid); jianshu(rc(i),mid+1,r); c[i].a = gcd(c[lc(i)].a,c[rc(i)].a); } void rd() { scanf("%d",&n); for(int i = 1; i <= n; i ++) scanf("%d",&a[i]); jianshu(1,1,n); for(int i = 1; i <= n; i ++) f[i][0] = a[i]; for(int j = 1; j <= 20; j ++) for(int i = 1; i <= n; i ++) if(i + (1<<j) - 1 <= n) { f[i][j] = min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } int qiu(int i,int l,int r,int x)//求区间gcd { if(l <= c[i].l && c[i].r <= r) { if(c[i].a % x == 0) return 1; else return 0; } if(l > c[i].r || r < c[i].l) return 1; if(!qiu(lc(i),l,r,x)) return 0; return qiu(rc(i),l,r,x); } int rmq(int l,int r) { int o = log2(r-l+1); return min(f[l][o],f[r-(1<<o)+1][o]); } bool pd(int l,int r) { int u = rmq(l,r); return qiu(1,l,r,u); } bool judge(int len) { for(int i = 1; i+len-1 <= n; i ++) { if(pd(i,i+len-1)) return 1; } return 0; } int ans[MAXN]; void wt(int len) { int cnt = 0; for(int i = 1; i+len-1 <= n; i ++) { if(pd(i,i+len-1)) { cnt ++; ans[cnt] = i; } } cout<<cnt<<" "<<len-1<<"\n"; for(int i = 1; i <= cnt; i ++) cout<<ans[i]<<" "; } int main() { rd(); int l = 1,r = n; //cout<<judge(5)<<"\n"; //return 0; while(l + 3 < r) { // cout<<"Orz\n"; int mid = (l+r)>>1; if(judge(mid)) l = mid; else r = mid; } //cout<<"Sooke tql"; for(int i = r; i >= l; i --) { if(judge(i)) { wt(i); return 0; } } return 0; } ```