【CF1325E】 Ehab's REAL Number Theory Problem（思维+最小环bfs）

题目：
思路：
如果一个数 $x$ 有三个不同的质约数 $p_{1}, p_{2}, p_{3}$ ，那么这个数至少有8个约数。
这是因为 $g c d (p_{1}, p_{3}) = 1, g c d (p_{2}, p_{3}) = 1$ ，那么 $g c d (p_{1} * p_{2}, p_{3}) = 1$ ，也就是说不可能存在两个质约数的乘积= $x$ （否则就会有 $p_{3} ∣ (p_{1} * p_{2}), g c d (p_{1} * p_{2}, p_{3})$ ）,再加上1和 $x$ 就至少有8个约数了。
所以题目的意思是说给出的 $a_{i}$ 都最多有两个质约数。
所谓完全平方数 $x$ ，可以理解为对 $x$ 进行完全质因子分解，每个质因子的出现次数都为偶次。
对 $a_{i}$ 进行完全质因子分解，只考虑出现奇数次的质因子，由于题目保证 $a_{i}$ 最多只有两个质约数，也就是出现奇数出的质因子最多只有两个。构造一个图，点的编号都是质数，边权是对应的 $a_{i}$ 。 $x$ 分解完后可能为1、1个质因子p、2个质因子p,q。在图中的连接情况对应的是：(1,1)、(1,p)、(p,q)，这样找到图中的最小环，环内点的数目即答案。因为环内每个点都出现了两次，这样就满足了完全平方数。
（1）自环(1,1)，或者两个点被连接了多次，这些情况可以直接判断答案。
（2）否则就是对于两个点只被直接连接一次的图，枚举 $1 ～ s q r t (m a x (a_{i}))$ 为起点bfs求最小环。
注意：若分解为两个质因子p和q，那么 $p * q \leq m a x (a_{i})$ ,即图中最大的质数为 $s q r t (m a x (a_{i}))$ ，只从 $\leq s q r t (m a x (a_{i}))$ 的质数为起点就可以找到答案。
自测样例：

6
2 3 5 6 12 40

对应的图：

ac代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int x, n, ans = INT_MAX;
struct node{
    int nxt, eid;
};
vector<node> edges[maxn];
map<pair<int, int>, int> mp;
bool vis[maxn];
int dis[maxn];
queue<int> q;
void Div(int x, int id)
{
    int p = 1, q = 1;
    for(int i = 2; i*i <= x; i++)
    {
        if(x%i==0)
        {
            int num = 0;
            while(x%i==0) num++, x/=i;
            if(num%2)
            {
                if(p==1) p = i;
                else q = i;
            }
        }
    }
    if(x!=1)
    {
        if(p==1) p = x;
        else q = x;
    }
    if(p==1&&q==1)
    {
        ans = min(ans, 1);
        return ;
    }
    mp[{p, q}]++;
    if(mp[{p, q}]>=2)
    {
        ans = min(ans, 2);
        return ;
    }
    edges[q].push_back({p, id});
    edges[p].push_back({q, id});
}
int bfs(int s)
{
    if(edges[s].empty()) return INT_MAX;
    memset(vis, false, sizeof vis);//记录边是否访问过
    memset(dis, 0, sizeof dis);
    while(!q.empty()) q.pop();
    q.push(s);
    dis[s] = 1;//标记起始点已被访问
    while(!q.empty())
    {
        int now = q.front(); q.pop();
        for(int i = 0; i < edges[now].size(); i++)
        {
            int nxt = edges[now][i].nxt, eid = edges[now][i].eid;
            if(vis[eid]) continue;//边不回返
            if(dis[nxt]) return dis[now]+dis[nxt]-1;
            vis[eid] = true;
            q.push(nxt);
            dis[nxt] = dis[now]+1;
        }
    }
    return INT_MAX;//未成环
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        Div(x, i);
    }
    if(ans!=INT_MAX) printf("%d\n", ans);
    else
    {
        for(int i = 1; i <= 1000; i++) ans = min(ans, bfs(i));
        if(ans==INT_MAX) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}