1775D - Friendly Spiders

题目链接：Friendly Spiders

        首先我们可以考虑暴力做法，那就是每两个蜘蛛判断一下gcd，如果不等于1，那就连条边，这样的话时间复杂度是O（n^2），显然超时，因此我们可以采用类似二分图的方法去建，首先把一个数的所有质因数分解，然后连一条边，将质因数+n，因为这代表虚点，因为我们要求的是蜘蛛之间的关系，可以通过它们有相同的质因数去建立关系，因此边就建完了，然后跑一遍bfs，最后倒着跑一遍dfs求方案数即可。

代码附上：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 6e5+5;
int n,st,ed;
int a[N];
int d[N];
vector<int>g[N];
vector<int>ans;void bfs(int sx){queue<int>q;q.push(sx);d[sx]=1;while(!q.empty()){int x=q.front();q.pop();for(const auto &y:g[x]){if(!d[y]){d[y]=d[x]+1;q.push(y);}}}return;
}void dfs(int x){if(x==st)return;for(const auto &y:g[x]){if(d[y]==d[x]-1){ans.push_back(y);dfs(y);return;}}
}void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>st>>ed;for(int i=1;i<=n;i++){int x=a[i];for(int j=2;j*j<=x;j++){if(x%j==0){g[i].push_back(n+j);g[n+j].push_back(i);while(x%j==0)x/=j;}}if(x>1){g[i].push_back(n+x);g[n+x].push_back(i);}}bfs(st);if(!d[ed]){cout<<-1<<"\n";return;}ans.push_back(ed);dfs(ed);reverse(ans.begin(),ans.end());cout<<(ans.size()+1)/2<<"\n";//除去虚点for(int i=0;i<ans.size();i++){if(ans[i]<=n)cout<<ans[i]<<" ";}cout<<"\n";return;}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;while(t--){solve();}return 0;
}