传送门

  • 题目:
  • 思路:
    如果一个数 x x x有三个不同的质约数 p 1 , p 2 , p 3 p_1, p_2, p_3 p1,p2,p3,那么这个数至少有8个约数。
    这是因为 g c d ( p 1 , p 3 ) = 1 , g c d ( p 2 , p 3 ) = 1 gcd(p_1,p_3)=1, gcd(p_2, p_3)=1 gcd(p1,p3)=1,gcd(p2,p3)=1,那么 g c d ( p 1 p 2 , p 3 ) = 1 gcd(p_1*p_2, p_3)=1 gcd(p1p2,p3)=1,也就是说不可能存在两个质约数的乘积= x x x(否则就会有 p 3 ( p 1 p 2 ) , g c d ( p 1 p 2 , p 3 ) p_3|(p_1*p_2),gcd(p_1*p_2, p_3) p3(p1p2),gcd(p1p2,p3)),再加上1和 x x x就至少有8个约数了。
    所以题目的意思是说给出的 a i a_i ai都最多有两个质约数。
    所谓完全平方数 x x x,可以理解为对 x x x进行完全质因子分解,每个质因子的出现次数都为偶次。
    a i a_i ai进行完全质因子分解,只考虑出现奇数次的质因子,由于题目保证 a i a_i ai最多只有两个质约数,也就是出现奇数出的质因子最多只有两个。构造一个图,点的编号都是质数,边权是对应的 a i a_i ai x x 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 ) ) 1~sqrt(max(a_i)) 1sqrt(max(ai))为起点bfs求最小环。
    注意:若分解为两个质因子p和q,那么 p q m a x ( a i ) p*q≤max(a_i) pqmax(ai),即图中最大的质数为 s q r t ( m a x ( a i ) ) sqrt(max(a_i)) sqrt(max(ai)),只从 s q r t ( m a x ( a i ) ) ≤sqrt(max(a_i)) sqrt(max(ai))的质数为起点就可以找到答案。
    自测样例:
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;
}