Ant colony (Codeforces 474F)
Tags: Math, number theory

Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l and r (1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si). After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.In order to choose the best sequence, Mole gives you t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.

Input: The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony. The second line contains n integers s1, s2, ..., sn (1 ≤ si ≤ 109), the strengths of the ants. The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases. Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.

Output: Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [li, ri].

Note: In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.

Sample Inputs:
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5

Sample Outputs:
4
4
1
1

Solution (Python):
import decimal
import heapq
import math
import os
import sys
from array import array
from collections import Counter, deque
from io import BytesIO, IOBase
import bisect
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ints_get():
    return map(int, input().strip().split())

def list_get():
    return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
    return list(map(str, sys.stdin.readline().strip().split()))

def output(to_be_printed, end='\n'):
    sys.stdout.write(str(to_be_printed) + end)

def ipn():
    return int(input())

def segfunc(x, y):
    if x == -1:
        return y
    elif y == -1:
        return x
    return math.gcd(x, y)

class SegmentTree(object):

    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for (i, v) in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def main():
    n = ipn()
    s = list_get()
    v = s.copy()
    t = 1 << (n - 1).bit_length()
    for _ in range(t - n):
        v.append(-1)
    tree = SegmentTree(v, segfunc, -1)
    dic = {}
    for i in range(n):
        if s[i] in dic:
            dic[s[i]].append(i + 1)
        else:
            dic[s[i]] = [i + 1]
    for _ in range(ipn()):
        (l, r) = ints_get()
        val = tree.sum(l - 1, r)
        out = r - l + 1
        if val in dic:
            x = bisect.bisect_left(dic[val], l)
            y = bisect.bisect_right(dic[val], r)
            out -= y - x
        print(out)
    return
if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print('Invalid argument to calculate n!')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print('Invalid argument to calculate n^(-1)')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print('Invalid argument to calculate (n^(-1))!')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]

class Combination:

    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

class SegmentTree:

    def __init__(self, data, default=0, func=lambda a, b: math.gcd(a, b)):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
from collections import defaultdict as dict
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound

def findFrequency(arr, n, left, right, element):
    a = lower_bound(store[element], left)
    b = upper_bound(store[element], right)
    return b - a
n = int(input())
arr = list(map(int, input().split()))
store = dict(list)
for i in range(n):
    store[arr[i]].append(i + 1)
t = int(input())
st = SegmentTree(arr)
for i in range(t):
    (l, r) = map(int, input().split())
    g = st.query(l - 1, r - 1)
    c = findFrequency(arr, n, l, r, g)
    print(r - l + 1 - c)

Solution (Python):
import sys, threading, os, io
import math
import time
from os import path
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
import heapq
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
from io import BytesIO, IOBase

def lcm(a, b):
    return a * b // math.gcd(a, b)
si = lambda : str(input())
ii = lambda : int(input())
mii = lambda : map(int, input().split())
lmii = lambda : list(map(int, input().split()))
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
from math import gcd

class SegmentTree:

    def __init__(self, data, default=0, func=gcd):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
if os.path.exists('/Users/nitishkumar/Documents/Template_Codes/Python/CP/Codeforces/input.txt'):
    sys.stdin = open('/Users/nitishkumar/Documents/Template_Codes/Python/CP/Codeforces/input.txt', 'r')
    sys.stdout = open('/Users/nitishkumar/Documents/Template_Codes/Python/CP/Codeforces/output.txt', 'w')
    start_time = time.time()
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = ii()
s = lmii()
d = defaultdict(lambda : [])
for i in range(n):
    d[s[i]].append(i)

def cnt(x, left, right):
    l = bisect_left(d[x], left)
    r = bisect_right(d[x], right)
    return r - l
seg = SegmentTree(s)
for _ in range(ii()):
    (l, r) = lmii()
    l -= 1
    r -= 1
    g = seg.query(l, r + 1)
    print(r - l + 1 - cnt(g, l, r))