题解 Friendly Spiders

发布时间 2023-07-17 21:29:33作者: HQJ2007

Friendly Spiders

带有技巧的最短路。

如果 \(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;
}