Pair of Numbers (Codeforces 359D)
Tags: Math, two pointers

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.

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

Sample Inputs:
5
4 6 9 3 6

5
1 3 5 7 9

5
2 3 5 7 11

Sample Outputs:
1 3
2

1 4
1

5 0
1 2 3 4 5

Solution (Python):
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict, Counter
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : i4nt(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def main():
    n = int(input()) + 1
    a = [1] + list(map(int, input().split())) + [1]
    visited = [False] * n
    longest = 0
    start = list(range(1, n))
    for i in range(1, n):
        if visited[i] == False:
            (l, r) = (i, i)
            divisor = a[i]
            if divisor == 1:
                longest = n - 2
                start = [1]
                break
            while a[l - 1] % divisor == 0:
                l -= 1
            while a[r + 1] % divisor == 0:
                r += 1
                visited[r] = True
            length = r - l
            if length > longest:
                longest = length
                start = [l]
            elif length == longest and length != 0:
                start.append(l)
    print(len(start), longest)
    print(*start)
if __name__ == '__main__':
    t = 1
    while t > 0:
        main()
        t -= 1

Solution (Python):
n = int(input()) + 1
t = [1] + list(map(int, input().split())) + [1]
p = [True] * n
(s, q) = (0, list(range(1, n)))
for i in range(1, n):
    if p[i]:
        a = b = i
        d = t[i]
        if d == 1:
            (s, q) = (n - 2, [1])
            break
        while t[a - 1] % d == 0:
            a -= 1
        while t[b + 1] % d == 0:
            b += 1
            p[b] = False
        d = b - a
        if d > s:
            (s, q) = (d, [a])
        elif d == s != 0:
            q.append(a)
print(len(q), s)
print(' '.join(map(str, q)))

Solution (Python):
import math
''
''
''

def prob():
    n = int(input())
    n += 1
    l = [1]
    l += [int(x) for x in input().split()]
    l += [1]
    p = [True] * n
    s = 0
    q = [i for i in range(1, n)]
    for i in range(1, n):
        if p[i]:
            a = i
            b = i
            d = l[i]
            if d == 1:
                (s, q) = (n - 2, [1])
                break
            while l[a - 1] % d == 0:
                a -= 1
            while l[b + 1] % d == 0:
                b += 1
                p[b] = False
            d = b - a
            if d > s:
                (s, q) = (d, [a])
            elif d == s and s != 0:
                q.append(a)
    print(len(q), s)
    print(*q)
t = 1
for _ in range(0, t):
    prob()