[codeforces] 359D Pair of Numbers

原题

RMQ st表棵题

要想让一个区间里的所有数都可以整除其中一个数，那么他一定是这个区间内的最小值，并且同时是这个区间的gcd。然后这个问题就转化成了RMQ问题。

维护两个st表，分别是最小值和gcd，然后二分最长区间长度，用st表check即可。

#include<cstdio>

#include<algorithm>

#include<cmath>

#define N 300010

using namespace std;

int n,a[N],mn[N][20],gd[N][20],l,r,mid,cnt,ans[N],p;

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;

    if (j=='-') fu=-1,j=getchar();

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

int gcd(int x,int y)

{

    return !y?x:gcd(y,x%y);

}

int check(int x)

{

    int p=log2(x),m,g,cct=0;

    if (p<0) return 0;

    for (int i=1;i+x<=n;i++)

    {

	m=min(mn[i][p],mn[i+x-(1<<p)+1][p]);

	g=gcd(gd[i][p],gd[i+x-(1<<p)+1][p]);

	if (m==g) ans[++cct]=i;

    }

    return cct;

}

int main()

{

    while (~scanf("%d",&n))

    {

	r=n;

	l=0;

	cnt=0;

	for (int i=1;i<=n;i++) a[i]=read(),mn[i][0]=gd[i][0]=a[i];

	for (int i=1;i<20;i++)

	    for (int j=1;j+(1<<(i-1))<=n;j++)

	    {

		mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]);

		gd[j][i]=gcd(gd[j][i-1],gd[j+(1<<(i-1))][i-1]);

	    }

	while (l!=r)

	{

	    mid=(l+r+1)>>1;

	    p=check(mid);

	    if (p) l=mid,cnt=p;

	    else r=mid-1;

	}

	if (!l)

	{

	    cnt=n;

	    for (int i=1;i<=n;i++)

		ans[i]=i;

	}

	printf("%d %d\n",cnt,l);

	for (int i=1;i<=cnt;i++)

	    printf("%d%c",ans[i]," \n"[i==cnt]);

    }

    return 0;

}