Cut (Codeforces 1516D)
Tags: DP, two pointers

This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array $$$a$$$ of length $$$n$$$ written on it, and then he does the following:  he picks a range $$$(l, r)$$$ and cuts the subsegment $$$a_l, a_{l + 1}, \ldots, a_r$$$ out, removing the rest of the array.  he then cuts this range into multiple subranges.  to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their least common multiple (LCM). Formally, he partitions the elements of $$$a_l, a_{l + 1}, \ldots, a_r$$$ into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for $$$q$$$ independent ranges $$$(l, r)$$$, tell Baby Ehab the minimum number of subarrays he needs.

Input: The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — the length of the array $$$a$$$ and the number of queries.The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the elements of the array $$$a$$$.Each of the next $$$q$$$ lines contains $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of this query's interval.

Output: For each query, print its answer on a new line.

Note: The first query asks about the whole array. You can partition it into $$$[2]$$$, $$$[3,10,7]$$$, and $$$[5,14]$$$. The first subrange has product and LCM equal to $$$2$$$. The second has product and LCM equal to $$$210$$$. And the third has product and LCM equal to $$$70$$$. Another possible partitioning is $$$[2,3]$$$, $$$[10,7]$$$, and $$$[5,14]$$$.The second query asks about the range $$$(2,4)$$$. Its product is equal to its LCM, so you don't need to partition it further.The last query asks about the range $$$(3,5)$$$. You can partition it into $$$[10,7]$$$ and $$$[5]$$$.

Sample Inputs:
6 3
2 3 10 7 5 14
1 6
2 4
3 5

Sample Outputs:
3
1
2

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_right
prime_size = 10 ** 5 + 10
primes = []
sfc = [i for i in range(prime_size)]
for i in range(2, prime_size):
    if sfc[i] == i:
        primes.append(i)
    pt = 0
    while pt < len(primes) and primes[pt] * i < prime_size and (primes[pt] <= i):
        sfc[primes[pt] * i] = primes[pt]
        pt += 1

def main(case):
    (n, q) = map(int, input().split())
    arr = list(map(int, input().split()))
    dp = [[n] * n for _ in range(17)]
    last = [n] * prime_size
    for i in range(n - 1, -1, -1):
        mn = n
        if i < n - 1:
            mn = min(mn, dp[0][i + 1])
        fc = arr[i]
        while fc >= 2:
            mn = min(mn, last[sfc[fc]])
            last[sfc[fc]] = i
            div = sfc[fc]
            while fc % div == 0:
                fc //= div
        dp[0][i] = mn
    for i in range(1, 17):
        for j in range(n):
            if dp[i - 1][j] == n:
                dp[i][j] = n
            else:
                dp[i][j] = dp[i - 1][dp[i - 1][j]]
    for _ in range(q):
        (a, b) = map(int, input().split())
        a -= 1
        b -= 1
        ans = 1
        for i in range(16, -1, -1):
            if a < b and dp[i][a] <= b:
                ans += 2 ** i
                a = dp[i][a]
        print(ans)
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')
if __name__ == '__main__':
    for _ in range(1):
        main(_ + 1)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def I():
    return int(input())

def LI():
    return [int(i) for i in input().split()]

def LI_():
    return [int(i) - 1 for i in input().split()]
(n, q) = LI()
prime_last_appear_at = dict()
dp = [[n] * (n + 1) for i in range(18)]
arr = LI()
have_primes = [[] for _ in range(10 ** 5 + 3)]
for p in range(2, 10 ** 5 + 2):
    if not have_primes[p]:
        prime_last_appear_at[p] = n
        i = p
        while i < len(have_primes):
            have_primes[i].append(p)
            i += p
for i in range(n - 1, -1, -1):
    dp[0][i] = dp[0][i + 1]
    for p in have_primes[arr[i]]:
        dp[0][i] = min(dp[0][i], prime_last_appear_at[p])
        prime_last_appear_at[p] = i
for i in range(1, len(dp)):
    for j in range(n):
        dp[i][j] = dp[i - 1][dp[i - 1][j]]
for _ in range(q):
    (l, r) = LI_()
    cur = l
    res = 1
    for jump in range(len(dp) - 1, -1, -1):
        if dp[jump][cur] <= r:
            res += 1 << jump
            cur = dp[jump][cur]
    print(res)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def I():
    return int(input())

def LI():
    return [int(i) for i in input().split()]

def LI_():
    return [int(i) - 1 for i in input().split()]
(n, q) = LI()
prime_last_appear_at = dict()
dp = [[n] * (n + 1) for i in range(18)]
arr = LI()
have_primes = [[] for _ in range(10 ** 5 + 3)]
for p in range(2, 10 ** 5 + 2):
    if not have_primes[p]:
        prime_last_appear_at[p] = n
        i = p
        while i < len(have_primes):
            have_primes[i].append(p)
            i += p
for i in range(n - 1, -1, -1):
    dp[0][i] = dp[0][i + 1]
    for p in have_primes[arr[i]]:
        dp[0][i] = min(dp[0][i], prime_last_appear_at[p])
        prime_last_appear_at[p] = i
for i in range(1, len(dp)):
    for j in range(n):
        dp[i][j] = dp[i - 1][dp[i - 1][j]]
for _ in range(q):
    (l, r) = LI_()
    cur = l
    res = 1
    for jump in range(len(dp) - 1, -1, -1):
        if dp[jump][cur] <= r:
            res += 1 << jump
            cur = dp[jump][cur]
    print(res)