← 返回题目列表

AtCoder · tkppc6_2_j

J. 公约数最短路径查询

中文机器翻译题面 查看原题

配点 : 800 点

問題文

N 我有一个无向顶点图。该图各边的信息是长度 使用 N 序列 我收到了 A 表示如下。

  • 任何整数对 如果 (i,j)\ (1 \leq i \lt j \leq N) , 从未连接到
    • A_i 和 在 A_j 不相交,则顶点 i 和顶点 j 之间没有边。
    • A_i 和 在 A_j 是 时间保证在 1 如果你的公约数大于 顶点为 x 顶点为 i 和顶点 j 之间的长度 x 边存在。

以下查询 您将获得 Q 件,请按顺序处理。

  • 顶点对 判断 (S,T) 。 来自行S 和 在 T 是否串联,如果串联 打印到 S 假设一直下雨,直到 T 的最短路径的长度。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 2 \times 10^3
  • 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
  • 在每个查询中,1 \leq S,T \leq N 和 S \neq T 满意 如果正确答案是满足
  • 所有输入均为整数

部分点

  • Q=1 的数据集,500 点。

注意

当提交仅针对部分点的代码时, 我们建议添加一个进程,如果该值大于Q 是 时间保证在 1 ,该进程将立即终止。


入力

输入是按以下格式从标准输入给出的。

N Q
A_1 A_2 \ldots A_N
\text{query}_1
\text{query}_2
\hspace{0.4cm}\vdots
\text{query}_Q

i 查询内容为 它由 \text{query}_i 表示,其内容按以下格式给出。

S T

出力

Q 跨线输出。i 在线 来自 i 输出查询的答案如下。 如果

  • S 和 在 T 连接起来,则 输出到S 假设一直下雨,直到 T 的最短路径的长度。 如果
  • S 和 在 T 未连接,则 输出-1 。

入力例 1

3 3
10 6 21
1 2
2 3
1 3

出力例 1

2
3
5

给出 N=3 顶点图包含以下内容 2 书的两侧被拉伸。 连接

  • 頂点 1 和顶点 2 ,长度 2 侧面
  • 頂点 2 和顶点 3 ,长度 3 侧面

因此,每个查询的答案如下。

  • 1 查询中询问的顶点 1 和顶点 2 的最短距离是顶点 等于直接连接 1 和顶点 2 的边的长度,其值为 连接 2 。
  • 2 查询中询问的顶点 2 和顶点 3 的最短距离是顶点 等于直接连接 2 和顶点 3 的边的长度,其值为 连接 3 。
  • 3 查询中询问的顶点 1 和顶点 3 的最短距离是顶点 等于直接连接 1,2 的边的长度和顶点 它等于连接 2,3 的边的长度之和,其值为 5 。

入力例 2

2 1
1 1
1 2

出力例 2

-1

在给定的图中,顶点 1 和顶点 2 未绑定,因此 输出-1 。

请注意,此输入满足部分点约束。


入力例 3

8 5
10 465 800 966 393 217 556 279
7 6
6 4
4 1
6 2
1 6

出力例 3

9
7
2
10
9

原案: primenumber_zz 设