満点解の解説をします。

まず、\(\max(A)\) 以下の素数のみを頂点とした有向グラフを構築します。任意の頂点対 \((x,y)\) について、\(x,y\) を共に素因数として含むような要素 \(A_i\) が存在する場合に限り \(x\) から \(y\) に向けて重み \(y\) の辺を張ります。このグラフ上で任意の頂点対について最短距離を求めたあと、クエリごとに始点、終点となる頂点数を全探索することで \(O(\max(A)^2+(N+Q)\log^2(\max(A)))\) でこの問題を解くことができます。

しかし、このままでは実行制限時間には間に合いません。そこで、上記のグラフの頂点数を削減します。

よく考えると、\(\sqrt{\max(A)}\) より大きい頂点同士には直接辺が張られないことが分かります。そのため \(\sqrt{\max(A)}\) 以下の頂点対について最短距離を求めたあと、適切にクエリ毎に復元をする方針が有力です。

まず、\(\sqrt{\max(A)}\) 以下の素数のみからなる辺数 \(0\) の有向グラフを改めて用意します。このグラフの頂点数 \(P\) は、素数定理より \(\frac{\sqrt{\max(A)}}{\log(\sqrt{\max(A)})}\) の定数倍に収まり、実際には \(168\) という値を取ります。

次に、用意したグラフに辺を張っていきます。これは、以下の手順により高速に行うことができます。

1. 長さ \(\max(A)\) の二次元配列 \(\text{mem}\) を用意し、\(i=1,2,\ldots,N\) について以下のことを行う。
   • \(A_i\) の素因数が、順に \(p_1,p_2,\ldots,p_k\) であるとする。このとき、\(l=p_1,p_2,\ldots,p_k\), \(r=p_1,p_2,\ldots,p_k\) について、以下の操作を行う。
     • \(l,r\) が共に \(\sqrt{\max(A)}\) 以下でかつ \(l\) から \(r\) に向かう辺が存在しない場合、\(l\) から \(r\) に向かう重み \(r\) の辺を張る。
     • そうでなく、\(l \lt r\) であるなら、\(\text{mem}[r]\) に \(l\) を追加する。
2. \(i=1,2,\ldots,\max(A)\) の順に以下のことを行う。
   1. \(\text{mem}[i]\) から重複した要素を取り除く。
   2. \(\text{mem}[i]\) に含まれる要素のペア \((l,r)\) のうち、\(l\) から \(r\) に向かう辺が存在しないものすべてについて新たに \(l\) から \(r\) に向かう重み \(r+i\) の辺を張る。

1.の計算量は明らかに \(O(N \log^2(\max(A)))\) です。また、2.のパートも Union-Find 木などを用いて適切に高速化することで、合計 \(O(P^2+N \log^2(\max(A)))\) などで解くことが可能です。

このような処理をして最大 \(O(P^2)\) 辺を持つグラフを構築した上で、\(P^2\) 個ある全ての頂点対に対して最短距離を求めます。これはワーシャルフロイド法を用いることで \(O(P^3)\) で行うことができます。

最後に、クエリが与えられるごとに最短経路の長さを求めます。これは、\(A_S\) の素因数から始めて一番最初に経由する \(\sqrt{\max(A)}\) 以下の素数、および \(A_T\) に到達する際に一番最後に経由する \(\sqrt{\max(A)}\) 以下の素数を全探索すればよいです。これはクエリあたり \(O(P^2)\) で、十分高速です。

よってこの問題を解くことができました。なお、コーナーケースには十分注意してください。例えばクエリごとに最短経路の長さを求める際、\(\sqrt{\max(A)}\) 以下の素数を一度も経由しない場合も考慮するべきです。

実装例 (C++)