带有技巧的最短路。
如果 \(u\) 能到 \(v\)，说明 \(\gcd(u,v)>1\)，也就是有相同因子。
所以我们考虑对于每个数 \(u\)，向他的所有质因子连一条长度为 \(1\) 的边，这样我们从 \(u\) 到 \(v\) 需要走两步，最终答案除以 \(2\) 即可。
每次遇到一个新的因子，都要新建节点。
需要注意的是，如果 \(u\) 的质因子中有真实存在的点，那么边权要设为 2，否则会少算。
最后跑一边最短路或 BFS 就行了。
复杂度 \(O(n \log n)\)。
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 5, inf = INT_MAX >> 2;
int n, a[N], s, t, dis[N], vis[N], pre[N], id[N], id2[N], tot;
struct node{
int v, w;
node(int v = 0, int w = 0):v(v), w(w){}
};
vector<node> adj[N];
void add(int u, int v, int w) {
adj[u].push_back(node(v, w));
adj[v].push_back(node(u, w));
}
void get(int w) {
int x = a[w];
for (int i = 2; i <= sqrt(x); ++i) {
if (x % i == 0) {
if (vis[i]) add(w, id[i], 2);
if (!id2[i]) id2[i] = ++tot;
add(w, id2[i], 1);
while (x % i == 0) x /= i;
}
}
if (x != 1) {
if (vis[x]) add(w, id[x], 2);
if (!id2[x]) id2[x] = ++tot;
add(w, id2[x], 1);
}
}
queue<int> q;
stack<int> st;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
tot = n;
for (int i = 1; i <= n; ++i) {
cin >> a[i]; id[a[i]] = i; vis[a[i]] = 1;
get(i);
}
for (int i = 1; i <= tot; ++i) dis[i] = inf;
cin >> s >> t;
dis[s] = 2;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i].v, w = adj[u][i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pre[v] = u;
q.push(v);
}
}
}
if (dis[t] == inf) {
cout << -1 << endl;
return 0;
}
cout << dis[t] / 2 << endl;
int cur = t;
while (cur != s) {
st.push(cur);
cur = pre[cur];
}
st.push(s);
while (!st.empty()) {
while (st.top() > n) st.pop();
cout << st.top() << " ";
st.pop();
}
cout << endl;
return 0;
}