301898: CF359D. Pair of Numbers

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Pair of Numbers

题意翻译

### 题目描述 $ Simon $ 有一个长度为 $ N $ 的正整数数列 $ a_1 , a_2 , \cdots , a_n $ ,现在他想找到这个数列中最长的一个区间,满足区间中有一个数 $ x $ 可以整除区间中任意数。 ### 输入格式 第一行有一个正整数 $N$ $(1 \leq N \leq 3 \times 10^5)$ ,表示数列的长度; 第二行有 $N$ 个正整数 $ a_1 , a_2 , \cdots , a_n $ $(1 \leq a_i \leq 10^6)$ ,即为给出的数列。 ### 输出格式 第一行输出两个正整数 $cnt~,~len$ ,表示满足要求的最长区间的个数与长度。 第二行输出 $ cnt $ 个升序排列的正整数,表示所有满足要求的最长区间的左端点。 这里,区间的长度定义为**右端点减左端点**。

题目描述

Simon has an array $ a_{1},a_{2},...,a_{n} $ , 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: 1. there is integer $ j $ ( $ l<=j<=r $ ), such that all integers $ a_{l},a_{l+1},...,a_{r} $ are divisible by $ a_{j} $ ; 2. 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.

输入输出格式

输入格式


The first line contains integer $ n $ ( $ 1<=n<=3·10^{5} $ ). The second line contains $ n $ space-separated integers $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{6}) $ .

输出格式


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.

输入输出样例

输入样例 #1

5
4 6 9 3 6

输出样例 #1

1 3
2 

输入样例 #2

5
1 3 5 7 9

输出样例 #2

1 4
1 

输入样例 #3

5
2 3 5 7 11

输出样例 #3

5 0
1 2 3 4 5 

说明

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) $ .

Input

题意翻译

### 题目描述 $ Simon $ 有一个长度为 $ N $ 的正整数数列 $ a_1 , a_2 , \cdots , a_n $ ,现在他想找到这个数列中最长的一个区间,满足区间中有一个数 $ x $ 可以整除区间中任意数。 ### 输入格式 第一行有一个正整数 $N$ $(1 \leq N \leq 3 \times 10^5)$ ,表示数列的长度; 第二行有 $N$ 个正整数 $ a_1 , a_2 , \cdots , a_n $ $(1 \leq a_i \leq 10^6)$ ,即为给出的数列。 ### 输出格式 第一行输出两个正整数 $cnt~,~len$ ,表示满足要求的最长区间的个数与长度。 第二行输出 $ cnt $ 个升序排列的正整数,表示所有满足要求的最长区间的左端点。 这里,区间的长度定义为**右端点减左端点**。

加入题单

上一题 下一题 算法标签: