数字对

暴力

题面

她的面前浮现出一个长度为$n$的序列$\{ai\}$,她想找出一段区间$[L,R]$($1\leq L \leq R\leq n$)。
这个特殊区间满足,存在一个$k$($L\leq k\leq R$),并且对于任意的$i$($L\leq i \leq R$),$a_i$都能被$a_k$整除。这样的一个特殊区间$[L,R]$价值为$R-L$。
小$H$想知道序列中所有特殊区间的最大价值是多少,而有多少个这样的区间呢?这些
区间又分别是哪些呢?

• $30pts$ $n\leq30$
• $60pts$ $n\leq3000$
• $80pts$ $n\leq300000$
• $100pts$ $n\leq500000$
• $2s$时限

解析

• $30pts$算法
  略
• $60pts$算法
  线段树暴力维护$gcd$和$\max$，二分最大长度，复杂度$O(nlog^2n)$
• $80pts$算法
  改为用$ST$表维护
• $100pts$算法
  线段树求$gcd$算法？？？
  或者
  枚举中间点往两边拓展,遇到不能被整除的数就停。
  同时注意到被扩展到的数无需再次拓展。
  由于一点最多被拓展到两次，复杂度$O(2n)$
  （于是一道傻逼题就被暴力AC了)

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
int n,a[N],l,r,tot,ans=0,sol[N],cnt,now;
bool vis[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
il void work(re int i)
{
  if(vis[i]) return;vis[i]=1;
      l=r=i;
      while(l>1)
    {
      l--;
      if(a[l]%a[i]!=0) {l++;break;}
      else vis[l]=1;
    }
      while(r<n)
    {
      r++;
      if(a[r]%a[i]!=0) {r--;break;}
      else vis[r]=1;
    }
      if(ans<r-l) ans=r-l,sol[tot=1]=l;
      else if(ans==r-l) sol[++tot]=l;
}
int main()
{
  freopen("pair.in","r",stdin);
  freopen("pair.out","w",stdout);
  n=gi();
  tot=n;fp(i,1,n) sol[i]=i;
  fp(i,1,n) a[i]=gi();
  if(n>3000)
    {
      re int gaoshi=min((1e8/n),(n+100));
      fp(i,1,gaoshi-1) work(n/gaoshi*i);
      }
  fp(i,1,n) work(i);
  sort(sol+1,sol+1+tot);re int ysn=0;//printf("%d\n",tot);
  fp(i,1,tot) if(sol[i]==sol[i-1]) ysn++;
  printf("%d %d\n",tot-ysn,ans);
  fp(i,1,tot) if(sol[i]!=sol[i-1]) printf("%d ",sol[i]);
  printf("\n");
  fclose(stdin);
  fclose(stdout);
  return 0;
}