CF1325E Ehab's REAL Number Theory Problem（bfs求最小环）

题意

给定一个数组 ${a_{i}}$ ，求最少的数的个数，使得它们的乘积为平方数。
其中， $a_{i}$ 的因子不超过 $7$ 个
$n \leq 1 0^{5}, a_{i} \leq 1 0^{6}$

分析

设 $a_{i} = <munder> \prod j </munder> p_{j}^{k_{j}}$
那么 $a_{i}$ 的因子个数为 $<munder> \prod j </munder> (k_{j} + 1)$
因为 $a_{i}$ 的因子个数不超过 $7$ ，所以 $a_{i}$ 最多有两个质因子。
那么先将 $a_{i}$ 质因数分解，对于次数为偶数的质数舍去，这时候会有两种情况：

$a_{i}$ 有两个质因子 $p$ 和 $q$ ，从 $p$ 到 $q$ 连一条边
$a_{i}$ 只有一个质因子 $p$ ，从 $1$ 到 $p$ 连一条边

这样，我们要求的，其实是我们生成的无向图的最小环。
这个图最多有 $1 0^{5}$ 条边。
然鹅，我只学过 $f l o y d$ 求最小环，复杂度爆炸。
考虑一个包含 $a, b, c$ 三个点的最小环，假设 $b, c$ 相邻，设 $d i s_{i}$ 为 $a$ 到 $i$ 的最短路距离，那么环的大小为 $d i s_{b} + d i s_{c} + 1$ 。
于是我们可以枚举 $a$ 点，从每个 $a$ 点进行 $b f s$ （因为边权为 $1$ )
$b f s$ 过程中，假设当前边是 $(b, c)$ ，如果 $c$ 被访问过，说明加入 $(b, c)$ 这条边会形成一个环。
这样，我们将复杂度降到了 $O (n^{2})$
然鹅， $n^{2}$ 也是爆炸啊。
注意到（~~没注意到~~，一个环不可能都是大素数，至少有一个小于 $1000$ 的素数，于是我们枚举小于 $1000$ 的素数即可。复杂度极低。

代码如下

#include <bits/stdc++.h>
#define N 1000005
#define M 200005
using namespace std;
typedef long long LL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
struct node{
	int a, b, c, n;
}d[M * 2];
LL z = 1, t;
int p[N], x[N], cnt, maxn = N - 5, tot = 1, num[N], ret, ans = (1 << 30);
int dep[M], h[M], v[M * 2];
void cr(int a, int b){
	d[++tot].a = a; d[tot].b = b; d[tot].n = h[a]; h[a] = tot;
}
void bfs(int a){
	int i, b;
	queue<int> q;
	memset(dep, 0, sizeof(dep));
	memset(v, 0, sizeof(v));
	dep[a] = 1;
	q.push(a);
	while(!q.empty()){
		a = q.front(); q.pop();
		for(i = h[a]; i; i = d[i].n){
			if(v[i]) continue;
			v[i] = v[i ^ 1] = 1;
			b = d[i].b;
			if(!dep[b]){
				dep[b] = dep[a] + 1;
				q.push(b);
			}
			else{
				ans = min(ans, dep[a] + dep[b] - 1);
			}
		}
	}
}
int main(){
	int i, j, n, m, v, a, b, k;
	for(i = 2; i <= maxn; i++){
		if(!x[i]) x[i] = p[++cnt] = i;
		for(j = 1; j <= cnt; j++){
			t = z * p[j] * i;
			if(t > maxn) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
		}
	}
	scanf("%d", &n);
	for(i = 1; i <= n; i++){
		scanf("%d", &v);
		j = sqrt(v);
		if(j * j == v){
			printf("1");
			return 0;
		}
		a = x[v]; k = 0;
		while(v % a == 0) v /= a, k++;
		if(k % 2 == 0) a = 1;
		if(v == 1) b = 1;
		else{
			b = x[v]; k = 0;
			while(v % b == 0) v /= b, k++;
			if(k % 2 == 0) b = 1;
		}
		if(!num[a]) num[a] = ++ret;
		if(!num[b]) num[b] = ++ret;
		cr(num[a], num[b]);
		cr(num[b], num[a]);
	}
	for(i = 1; i <= 1000; i++){
		if(!num[i]) continue;
		bfs(num[i]);
	}
	if(ans != (1 << 30)) printf("%d", ans);
	else printf("-1");
	return 0;
}