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