problem
给一些数，每个的因数个数不超过 7，求最少选出多少个，使得乘积为完全平方。无解输出 −1。\(n=10^5,V=10^6\)。
solution
如果一个数有三个不同的质因子，那么它至少有 8 个约数；如果一个数有平方因子，我们可以除掉。
所以任何数都可以写成下面三种形式：（\(p,q\) 为质数）
- \(1\)（游戏结束）
- \(p\)（连边 \(1\sim p\)）
- \(p\times q\)（连边 \(p\sim q\)）
将每个质因子看做一个点，将数字当成边如上连边。那么我们要找这个图中的最小环（如果一个质数出现四次一定能拆）。
1. floyed
floyed 可以 \(O(n^3)\) 求最小环。
伪代码如下：
for k in range(1,n):
for i in range(1,n):
for j in range(1,n):
ans=min(ans,f[i][j]+g[i][k]+g[k][j])
for i in range(1,n):
for j in range(1,n):
f[i][j]=min(f[i][j],f[i][k]+f[k][j])
就是强制经过 k 点的环，枚举 k 点两边接着什么。f[i][j] 的路径上的点编号此时 <k。
2. dfs
dfs 可以 \(O(n^2)\) 求无向图最小环（正确性未知）。
枚举每个点作为根，搜一棵搜索树。对于每一条返祖边，当做一个环，统计答案。
之所以要枚举所有点，是因为会出现两个返租边套起来的问题，统计不到中间的环。
数据
8 9 # n=8,m=9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 8
2 7
答案明显为 1-2-7-8
3. bfs
bfs 可以在 \(O(n^2)\) 内求出无向无权图最小环。
考虑 bfs 建 bfs 树，考虑所有跨层边，考虑这个跨层边带来的最小环。
外层枚举根，那么内层求两点距离的时候不用管 LCA，直接 \(dep_u+dep_v+1\)。
本题
bfs。但是观察到不存在一个只由 \(>\sqrt{10^6}\) 组成的环。所以枚举根只需要枚举前 \(\sqrt{10^6}\) 个点。