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$。