Di-visible Confusion (Codeforces 1604C)
Tags: Math, number theory

YouKn0wWho has an integer sequence $$$a_1, a_2, \ldots, a_n$$$. He will perform the following operation until the sequence becomes empty: select an index $$$i$$$ such that $$$1 \le i \le |a|$$$ and $$$a_i$$$ is not divisible by $$$(i + 1)$$$, and erase this element from the sequence. Here $$$|a|$$$ is the length of sequence $$$a$$$ at the moment of operation. Note that the sequence $$$a$$$ changes and the next operation is performed on this changed sequence.For example, if $$$a=[3,5,4,5]$$$, then he can select $$$i = 2$$$, because $$$a_2 = 5$$$ is not divisible by $$$i+1 = 3$$$. After this operation the sequence is $$$[3,4,5]$$$.Help YouKn0wWho determine if it is possible to erase the whole sequence using the aforementioned operation.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$)  — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print "YES" (without quotes) if it is possible to erase the whole sequence using the aforementioned operation, print "NO" (without quotes) otherwise. You can print each letter in any register (upper or lower).

Note: In the first test case, YouKn0wWho can perform the following operations (the erased elements are underlined): $$$[1, \underline{2}, 3] \rightarrow [\underline{1}, 3] \rightarrow [\underline{3}] \rightarrow [\,].$$$In the second test case, it is impossible to erase the sequence as $$$i$$$ can only be $$$1$$$, and when $$$i=1$$$, $$$a_1 = 2$$$ is divisible by $$$i + 1 = 2$$$.

Sample Inputs:
5
3
1 2 3
1
2
2
7 7
10
384836991 191890310 576823355 782177068 404011431 818008580 954291757 160449218 155374934 840594328
8
6 69 696 69696 696969 6969696 69696969 696969696

Sample Outputs:
YES
NO
YES
YES
NO

Solution (Python):
from sys import stdin, stdout
from math import gcd
input = stdin.readline
print = stdout.write
for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if a[0] % 2 == 0:
        print('No\n')
    else:
        l = 2
        poss = True
        reached = False
        for j in range(n):
            if not reached:
                l = l * (j + 2) // gcd(l, j + 2)
            if l > 10 ** 9:
                reached = True
            if a[j] % l == 0:
                poss = False
                break
        if poss:
            print('Yes\n')
        else:
            print('No\n')

Solution (Python):
def compute_gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def compute_lcm(x, y):
    lcm = x * y // compute_gcd(x, y)
    return lcm
lcms = []
lcm_to_this_moment = 1
for i in range(1, 22):
    lcm_to_this_moment = compute_lcm(lcm_to_this_moment, i + 1)
    lcms.append(lcm_to_this_moment)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    flag = 1
    for (i, j) in zip(a, lcms[:n]):
        if i % j == 0:
            print('NO')
            flag = 0
            break
    if flag:
        print('YES')

Solution (Python):
import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        to = f(*args, **kwargs)
        if stack:
            return to
        else:
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        return to
                    to = stack[-1].send(to)
    return wrappedfunc

class Graphs:

    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes, colors, parity, level):
        global count
        if nodes == 1:
            colors[nodes] = -1
        elif len(self.graph[nodes]) == 1 and parity % 2 == 0:
            if q == 1:
                colors[nodes] = 1
            else:
                colors[nodes] = -1
                count += 1
        elif parity % 2 == 0:
            colors[nodes] = -1
        else:
            colors[nodes] = 1
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            new_level = level + 1
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes, colors, level - 1, new_level)

    def dfs(self, node):
        Visited = set()
        color = collections.defaultdict()
        self.dfs_utility(node, Visited, color, 0, 0)
        return color

    def bfs(self, node, f_node):
        count = float('inf')
        visited = set()
        level = 0
        if node not in visited:
            queue.append([node, level])
            visited.add(node)
        flag = 0
        while queue:
            parent = queue.popleft()
            if parent[0] == f_node:
                flag = 1
                count = min(count, parent[1])
            level = parent[1] + 1
            for item in self.graph[parent[0]]:
                if item not in visited:
                    queue.append([item, level])
                    visited.add(item)
        return count if flag else -1
        return False

class Tree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(node, lis):
    if node:
        inorder(node.left, lis)
        lis.append(node.data)
        inorder(node.right, lis)
    return lis

def leaf_node_sum(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.data
    return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
    if root is None:
        return -1
    if root.left is None and root.right is None:
        return 0
    return max(hight(root.left), hight(root.right)) + 1

class UF:
    """"""

    def __init__(self, N):
        """"""
        self._id = list(range(N))
        self._count = N
        self._rank = [0] * N

    def find(self, p):
        """"""
        id = self._id
        while p != id[p]:
            p = id[p]
        return p

    def count(self):
        """"""
        return self._count

    def connected(self, p, q):
        """"""
        return self.find(p) == self.find(q)

    def union(self, p, q):
        """"""
        id = self._id
        rank = self._rank
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        self._count -= 1
        if rank[i] < rank[j]:
            id[i] = j
        elif rank[i] > rank[j]:
            id[j] = i
        else:
            id[j] = i
            rank[i] += 1

    def add_roads(self):
        return set(self._id)

    def __str__(self):
        """"""
        return ' '.join([str(x) for x in self._id])

    def __repr__(self):
        """"""
        return 'UF(' + str(self) + ')'

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def p_sum(array):
    return list(itertools.accumulate(array))

def base_change(nn, bb):
    if nn == 0:
        return [0]
    digits = []
    while nn:
        digits.append(int(nn % bb))
        nn //= bb
    return digits[::-1]

def diophantine(a: int, b: int, c: int):
    (d, x, y) = extended_gcd(a, b)
    r = c // d
    return (r * x, r * y)

@bootstrap
def extended_gcd(a: int, b: int):
    if b == 0:
        (d, x, y) = (a, 1, 0)
    else:
        (d, p, q) = (yield extended_gcd(b, a % b))
        x = q
        y = p - q * (a // b)
    yield (d, x, y)
''
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, **kwargs):
        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))

def inp():
    return sys.stdin.readline().strip()

def map_inp(v_type):
    return map(v_type, inp().split())

def list_inp(v_type):
    return list(map_inp(v_type))

def find_gcd(lis):
    x = lis[0]
    for item in lis:
        x = math.gcd(item, x)
    return x
for _ in range(int(inp())):
    n = int(inp())
    arr = list_inp(int)
    if arr[0] % 2 == 0:
        print('NO')
    else:
        ind = 3
        temp = 2
        flag = 1
        for i in range(1, n):
            temp = temp * ind // math.gcd(temp, ind)
            if temp > 10 ** 9:
                break
            if arr[i] % ind == 0:
                if arr[i] % temp == 0:
                    flag = 0
                    break
            ind += 1
        if flag:
            print('YES')
        else:
            print('NO')