整除

(div.pas/c/cpp) 128MB 1s

给出一个长度为n的序列A，请你找出一个最长的区间使得这个区间内存在一个数字能被区间内所有数字整除（即存在对于所有，使得）。最长的区间可能有多个，所以还要输出最长的区间的个数。

输入格式

第1行为一个正整数 n。

第2行n个数为Ai。

输出格式

第一行两个整数，num和val，分别表示长度最长的区间的个数以及长度（定义为R-L）。

第二行num个整数，按升序输出每一个长度最长区间的左端点（从1开始标号）。

样例输入

4 6 9 3 6

样例输出

1 3

数据范围

————————————————————————

这道题我们可以按大小从小到达序

我们每次拿出数组中的最小值在原序列中左右拓展被拓展到的数明显不比当前数优

那么这些数就不用再拿来拓展了

这样复杂度就降到O（n）级别了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=550007;
LL v[M];
int n,q[M],sum,mx,f[M],l,r,x;
struct node{LL v;int pos;}e[M];
bool cmp(node a,node b){return a.v<b.v;}
int main()
{
    freopen("div.in","r",stdin);
    freopen("div.out","w",stdout);
     scanf("%d",&n);
     for(int i=1;i<=n;i++) scanf("%lld",&v[i]),e[i].v=v[i],e[i].pos=i;
     sort(e+1,e+1+n,cmp);
     for(int i=1;i<=n;i++)if(!f[e[i].pos]){
         x=l=r=e[i].pos;
        LL now=e[i].v;
         f[x]=1;
         while(l>1&&v[l-1]%now==0) l--,f[l]=1;
         while(r<n&&v[r+1]%now==0) r++,f[r]=1;
         if(r-l>mx) mx=r-l,q[sum=1]=l;
         else if(r-l==mx) q[++sum]=l;
     }
     sort(q+1,q+1+sum);
     printf("%d %d
",sum,mx);
     for(int i=1;i<=sum;i++) printf("%d ",q[i]);
    return 0;
}

View Code