308661: CF1553G. Common Divisor Graph
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Common Divisor Graph
题意翻译
给定一个包含 $n$ 个节点的图。第 $i$ 个节点都有权值 $a_i$,没有两个节点权值相同。节点 $i,j$ 之间有一条无向边仅当 $\gcd(a_i,a_j)>1$。 给定 $q$ 次询问,每次包含整数 $s,t$ 表示你希望从节点 $s$ 到达节点 $t$。为了到达那个节点,你可以进行下列操作任意次: - 选定一个节点 $i$。创造一个新的节点,该节点的权值为 $a_i\times(a_i+1)$,并按照上述规则连边。 对于每次询问,你都需要求出,至少需要多少次操作才能使节点 $s$ 能到达节点 $t$。询问互相独立。 $2\leq n\leq1.5\times10^5;1\leq q\leq3\times10^5;$ $2\leq a_i\leq10^6;$ 且如果 $i\not=j$,$a_i\not=a_j$。 $1\leq s,t\leq n;s\not=t;$题目描述
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.输入输出格式
输入格式
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.
输出格式
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} $ .
输入输出样例
输入样例 #1
3 3
2 10 3
1 2
1 3
2 3
输出样例 #1
0
1
1
输入样例 #2
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
输出样例 #2
0
1
0
1
0
1
0
1
1
1
1
2