题解 CF359D 【Pair of Numbers】
ChthollyTree
2019-03-29 16:25:51
因为一个区间满足条件
设为[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;
}
```