D. Pair of Numbers Codeforces Round #209 (Div. 2)

77 阅读 0 评论 51 点赞

我是靠谱客的博主魁梧铅笔，最近开发中收集的这篇文章主要介绍D. Pair of Numbers Codeforces Round #209 (Div. 2)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Simon has an array a1, a2, ..., an, consisting of n positive integers. Today Simon asked you to find a pair of integers l, r (1 ≤ l ≤ r ≤ n), such that the following conditions hold:

there is integer j (l ≤ j ≤ r), such that all integers al, al + 1, ..., ar are divisible by aj;
value r - l takes the maximum value among all pairs for which condition 1 is true;

Help Simon, find the required pair of numbers (l, r). If there are multiple required pairs find all of them.

Input

The first line contains integer n (1 ≤ n ≤ 3·105).

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 106).

Output

Print two integers in the first line — the number of required pairs and the maximum value of r - l. On the following line print all l values from optimal pairs in increasing order.

   Sample test(s) 
 

     input 
   
5
4 6 9 3 6

     output 
   
1 3
2 

     input 
   
5
1 3 5 7 9

     output 
   
1 4
1 

     input 
   
5
2 3 5 7 11

     output 
   
5 0
1 2 3 4 5 

Note

In the first sample the pair of numbers is right, as numbers 6, 9, 3 are divisible by 3.

In the second sample all numbers are divisible by number 1.

In the third sample all numbers are prime, so conditions 1 and 2 are true only for pairs of numbers (1, 1), (2, 2), (3, 3), (4, 4), (5, 5).

求出一个最长的序列，使得序列中存在一个所有数的公约数

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define N 300009

using namespace std;

int a[N];
int n;
int ans[N];

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

        int le,ri,tmp=-1,num=0;

        for(int i=1;i<=n;)
        {
            le=ri=i;

            while(le && a[le]%a[i]==0) le--;

            while(ri<=n && a[ri]%a[i]==0) ri++;

            i=ri;

            ri=ri-le-2;

            if(ri>tmp)
            {
                num=0;
                tmp=ri;
            }

            if(ri==tmp)
            ans[num++]=le+1;
        }

        printf("%d %dn",num,tmp);

        for(int i=0;i<num;i++)
        {
            if(i==0)
            cout<<ans[i];
            else
            cout<<" "<<ans[i];
        }

        cout<<endl;

    }

    return 0;
}