Common Divisor Graph (Codeforces 1553G)
Tags: Math, hashing

Consider a sequence of distinct integers $$$a_1, \ldots, a_n$$$, each representing one node of a graph. There is an edge between two nodes if the two values are not coprime, i. e. they have a common divisor greater than $$$1$$$.There are $$$q$$$ queries, in each query, you want to get from one given node $$$a_s$$$ to another $$$a_t$$$. In order to achieve that, you can choose an existing value $$$a_i$$$ and create new value $$$a_{n+1} = a_i \cdot (1 + a_i)$$$, with edges to all values that are not coprime with $$$a_{n+1}$$$. Also, $$$n$$$ gets increased by $$$1$$$. You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that $$$a_t$$$ is reachable from $$$a_s$$$?Queries are independent. In each query, you start with the initial sequence $$$a$$$ given in the input.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 150\,000$$$, $$$1 \leq q \leq 300\,000$$$) — the size of the sequence and the number of queries.The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \leq a_i \leq 10^6$$$, $$$a_i \neq a_j$$$ if $$$i \ne j$$$).The $$$j$$$-th of the following $$$q$$$ lines contains two distinct integers $$$s_j$$$ and $$$t_j$$$ ($$$1 \leq s_j, t_j \leq n$$$, $$$s_j \neq t_j$$$) — indices of nodes for $$$j$$$-th query.

Output: Print $$$q$$$ lines. The $$$j$$$-th line should contain one integer: the minimum number of new nodes you create in order to move from $$$a_{s_j}$$$ to $$$a_{t_j}$$$.

Note: In the first example, you can first create new value $$$2 \cdot 3 = 6$$$ or $$$10 \cdot 11 = 110$$$ or $$$3 \cdot 4 = 12$$$. None of that is needed in the first query because you can already get from $$$a_1 = 2$$$ to $$$a_2 = 10$$$.In the second query, it's optimal to first create $$$6$$$ or $$$12$$$. For example, creating $$$6$$$ makes it possible to get from $$$a_1 = 2$$$ to $$$a_3 = 3$$$ with a path $$$(2, 6, 3)$$$.  In the last query of the second example, we want to get from $$$a_3 = 7$$$ to $$$a_5 = 25$$$. One way to achieve that is to first create $$$6 \cdot 7 = 42$$$ and then create $$$25 \cdot 26 = 650$$$. The final graph has seven nodes and it contains a path from $$$a_3 = 7$$$ to $$$a_5 = 25$$$.

Sample Inputs:
3 3
2 10 3
1 2
1 3
2 3

5 12
3 8 7 6 25
1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5

Sample Outputs:
0
1
1

0
1
0
1
0
1
0
1
1
1
1
2

Solution (Python):
import itertools
from collections import defaultdict
from sys import stdin

def input():
    return next(stdin)[:-1]

def readline():
    return map(int, input().split())
primes = [2]
for q in range(3, 10 ** 3, 2):
    if all((q % p for p in primes)):
        primes.append(q)

def prime_divisors(n, primes=primes):
    ret = []
    for p in primes:
        if p * p > n:
            break
        (q, r) = divmod(n, p)
        if not r:
            ret.append(p)
        while not r:
            n = q
            (q, r) = divmod(n, p)
    if n > 1:
        ret.append(n)
    return ret

def test_prime_divisors():
    assert list(prime_divisors(6)) == [2, 3]
    assert list(prime_divisors(9)) == [3]
    assert list(prime_divisors(10)) == [2, 5]
    assert list(prime_divisors(7)) == [7]
    assert list(prime_divisors(997)) == [997]
    assert list(prime_divisors(1009)) == [1009]

class DSU:
    __slots__ = ('p',)

    def __init__(self):
        self.p = list(range(10 ** 6))

    def _get_root(self, a):
        while self.p[a] != a:
            a = self.p[a]
        return a

    def __setitem__(self, a, b):
        assert b <= a
        r = self._get_root(b)
        while a != r:
            (self.p[a], a) = (r, self.p[a])

    def __getitem__(self, a):
        self[a] = a
        return self.p[a]

def main():
    (n, q) = readline()
    a = list(readline())
    queries = (readline() for __ in range(q))
    min_divisor = list()
    dsu = DSU()
    for ai in a:
        (p, *rest) = prime_divisors(ai)
        min_divisor.append(p)
        for q in rest:
            dsu[q] = p
    for i in range(len(dsu.p)):
        dsu[i]
    dsu = dsu.p
    one = list()
    available = defaultdict(set)
    for (ai, p) in zip(a, min_divisor):
        p = dsu[p]
        components = sorted(set((dsu[q] for q in prime_divisors(ai + 1))))
        if p != dsu[2]:
            available[p].update(components)
        one.extend(itertools.combinations(components, 2))
    one = set(one)
    for (p, q) in one:
        assert p < q

    def av(p, q):
        return p in available[q]
    for (s, t) in queries:
        p = dsu[min_divisor[s - 1]]
        q = dsu[min_divisor[t - 1]]
        (p, q) = sorted((p, q))
        if p == q:
            print(0)
        elif dsu[2] in (p, q) or av(p, q) or av(q, p) or ((p, q) in one):
            print(1)
        else:
            print(2)
if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
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')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = ans * each % mod
    return ans

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(a, b):
    return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
    (components, visited) = ([], [False] * n)

    def dfs(start):
        (component, stack) = ([], [start])
        while stack:
            start = stack[-1]
            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)
            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)
        return component
    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))
    return components

def Sieve(limit=10 ** 6):
    isPrime = [1] * (limit + 1)
    isPrime[0] = isPrime[1] = 0
    for i in range(2, limit + 1):
        if isPrime[i] != 1:
            continue
        for j in range(i * i, limit + 1, i):
            isPrime[j] = i
    return isPrime
isPrime = Sieve(10 ** 6 + 2)

def prime_factors(n):
    if n < 2:
        return []
    result = []
    while isPrime[n] > 1:
        y = isPrime[n]
        result += [y]
        while n % y == 0:
            n //= y
    if n != 1:
        result += [n]
    return result
for _ in range(int(input()) if not True else 1):
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    graph = [[] for i in range(n)]
    px = {}
    for i in range(n):
        for p in prime_factors(a[i]):
            if p not in px:
                px[p] = i
            else:
                graph[i] += [px[p]]
                graph[px[p]] += [i]
    cp = connected_components(n, graph)
    comp_num = [0] * n
    for i in range(1, len(cp)):
        for j in cp[i]:
            comp_num[j] = i
    st2 = set()
    for i in range(len(cp)):
        for j in cp[i]:
            y = set()
            for prime in prime_factors(a[j] + 1):
                if prime in px:
                    st2.add((i, comp_num[px[prime]]))
                    y.add(comp_num[px[prime]])
            for y1 in y:
                for y2 in y:
                    if y1 != y2:
                        st2.add((y1, y2))
    for __ in range(q):
        (x, y) = map(int, input().split())
        x -= 1
        y -= 1
        if comp_num[x] == comp_num[y]:
            print(0)
            continue
        (p, q) = (comp_num[x], comp_num[y])
        if (p, q) in st2 or (q, p) in st2:
            print(1)
            continue
        print(2)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
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')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = ans * each % mod
    return ans

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(a, b):
    return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
    (components, visited) = ([], [False] * n)

    def dfs(start):
        (component, stack) = ([], [start])
        while stack:
            start = stack[-1]
            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)
            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)
        return component
    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))
    return components

def Sieve(limit=10 ** 6):
    """"""
    isPrime = [1] * (limit + 1)
    isPrime[0] = isPrime[1] = 0
    for i in range(2, limit + 1):
        if isPrime[i] != 1:
            continue
        for j in range(i * i, limit + 1, i):
            isPrime[j] = i
    return isPrime
isPrime = Sieve(10 ** 6 + 2)

def prime_factors(n):
    """"""
    if n < 2:
        return []
    result = []
    while isPrime[n] > 1:
        y = isPrime[n]
        result += [y]
        while n % y == 0:
            n //= y
    if n != 1:
        result += [n]
    return result
for _ in range(int(input()) if not True else 1):
    (n, q) = map(int, input().split())
    a = list(map(int, input().split()))
    graph = [[] for i in range(n)]
    px = {}
    for i in range(n):
        for p in prime_factors(a[i]):
            if p not in px:
                px[p] = i
            else:
                graph[i] += [px[p]]
                graph[px[p]] += [i]
    cp = connected_components(n, graph)
    comp_num = [0] * n
    for i in range(1, len(cp)):
        for j in cp[i]:
            comp_num[j] = i
    st2 = set()
    for i in range(len(cp)):
        for j in cp[i]:
            y = set()
            for prime in prime_factors(a[j] + 1):
                if prime in px:
                    st2.add((i, comp_num[px[prime]]))
                    y.add(comp_num[px[prime]])
            for y1 in y:
                for y2 in y:
                    if y1 != y2:
                        st2.add((y1, y2))
    for __ in range(q):
        (x, y) = map(int, input().split())
        x -= 1
        y -= 1
        if comp_num[x] == comp_num[y]:
            print(0)
            continue
        (p, q) = (comp_num[x], comp_num[y])
        if (p, q) in st2 or (q, p) in st2:
            print(1)
            continue
        print(2)