题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005;

int n,a[N],s,t;
bool f[N];
vector<int> primes;
vector<int> g[N*2];

queue<int> q;
int dist[N2],pre[N2];

void select(){ //预处理筛出所有质数 欧拉筛筛
for(int i=2;i<N;i++){
if(!f[i]) primes.push_back(i);
for(auto p : primes){
if(ip>=N) break;
f[ip] = 1;
if(i%p==0) break;
}
}
}

void build(){ //建图：每个节点向它的所有质因数连边
//原节点编号 1~n， 质因数节点：从小到大，编号从n+1开始
for(int i=1;i<=n;i++){
int x = a[i];
for(int j=2;j*j<=x;j++){
if(x%j!=0) continue;
while(x%j==0) x/=j;
int idj = lower_bound(primes.begin(),primes.end(),j) - primes.begin();
idj += n+1;
g[i].push_back(idj);
g[idj].push_back(i);
}
if(x!=1){
int idj = lower_bound(primes.begin(),primes.end(),x) - primes.begin();
idj += n+1;
g[i].push_back(idj);
g[idj].push_back(i);
}
}
}

void print(int u){
if(u==s){
cout << s;
return ;
}
print(pre[pre[u]]);
cout << " " << u;
}

void bfs(){
memset(dist, 0x3f, sizeof dist);
q.push(s);
dist[s] = 0;
pre[s] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
if(u==t){
cout << dist[t]/2 + 1 << "\n";
print(u);
return;
}
for(auto v : g[u]){
if(dist[u]+1 < dist[v]){
dist[v] = dist[u]+1;
pre[v] = u;
q.push(v);
}
}
}
cout << -1;
}

int main(){
cin >> n;
for(int i=1;i<=n;i++) cin>>a[i];
cin >> s >> t;

select();
build();
bfs();
return 0;

}