如何做关于橱柜网站,东莞建网站的公司,多域名一个网站备案,上海网站建设优化价格题目链接#xff1a;Friendly Spiders 首先我们可以考虑暴力做法#xff0c;那就是每两个蜘蛛判断一下gcd#xff0c;如果不等于1#xff0c;那就连条边#xff0c;这样的话时间复杂度是O#xff08;n^2#xff09;#xff0c;显然超时#xff0c;因此我们可以采用类似…题目链接Friendly Spiders 首先我们可以考虑暴力做法那就是每两个蜘蛛判断一下gcd如果不等于1那就连条边这样的话时间复杂度是On^2显然超时因此我们可以采用类似二分图的方法去建首先把一个数的所有质因数分解然后连一条边将质因数n因为这代表虚点因为我们要求的是蜘蛛之间的关系可以通过它们有相同的质因数去建立关系因此边就建完了然后跑一遍bfs最后倒着跑一遍dfs求方案数即可。
代码附上
#include bits/stdc.h
#define int long long
using namespace std;
const int inf 0x3f3f3f3f3f3f3f3f;
const int N 6e55;
int n,st,ed;
int a[N];
int d[N];
vectorintg[N];
vectorintans;void bfs(int sx){queueintq;q.push(sx);d[sx]1;while(!q.empty()){int xq.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(xst)return;for(const auto y:g[x]){if(d[y]d[x]-1){ans.push_back(y);dfs(y);return;}}
}void solve(){cinn;for(int i1;in;i)cina[i];cinsted;for(int i1;in;i){int xa[i];for(int j2;j*jx;j){if(x%j0){g[i].push_back(nj);g[nj].push_back(i);while(x%j0)x/j;}}if(x1){g[i].push_back(nx);g[nx].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 i0;ians.size();i){if(ans[i]n)coutans[i] ;}cout\n;return;}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t1;while(t--){solve();}return 0;
}
