P17897 [ICPC 2026 Nanchang I] Journey of GCD

题目描述

在神奇的 Numerian 魔法王国中,有 $n$ 座城市,每座城市都拥有自己的魔法能量值 $a_i$。国王在每两座城市之间都修建了双向道路,其中连接城市 $u$ 和城市 $v$ 的道路的守护符强度(Guardian Charm Degree,简称 GCD)等于 $\gcd(a_u,a_v)$,即两座城市魔法能量值的最大公约数。 旅行者从城市 $x$ 前往城市 $y$ 时,其旅程的魔法免疫指数(Magical Immunity Number,简称 MIN)等于所经过的所有道路中 GCD 的最小值。王国的皇家顾问认为一次旅程是“强免疫”的,当且仅当它的 MIN 达到了可能的最大值。 你的任务是回答国王的 $q$ 次询问。对于每次询问 $(x,y)$,输出从城市 $x$ 到城市 $y$ 的所有路径中,可能的最大 MIN。 特别地,如果 $x = y$,旅行者没有离开城市,此时 MIN 等于该城市自身的魔法能量值 $a_x$。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^6$)。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^6$),表示每座城市的魔法能量值。 接下来 $q$ 行,每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$),表示一次询问。

输出格式

对于每次询问,输出一行一个整数,表示可能的最大 MIN。

说明/提示

对于样例,魔法能量值 $a=[6,15,22,33,35,63]$。 第 1 组询问:最优路径为 $5 \to 6$,答案为 $\gcd(35,63)=7$。 第 2 组询问:最优路径为 $3 \to 4 \to 6 \to 5$,三条边的 GCD 分别为 $\gcd(22,33)=11$,$\gcd(33,63)=3$ 和 $\gcd(63,35)=7$,答案为 $\min(11,3,7)=3$。 第 3 组询问:由于 $x=y$,旅行者没有离开城市,答案为 $a_2=15$。