CodeForces-1325E Ehab's REAL Number Theory Problem（最小环）

传送门：CodeForces-1325E

思路分析

从n个数里面，选出最少的数，使得乘积为完全平方。
如果其中有1，那么答案肯定为1，如果有两个相同的数，答案也为1
首先，对于一个数，如果他自己的因数中存在完全平方数，那么可以将这个数除掉，对答案并没有影响
因为最多只有7个因数，所以一个数最多有两个素数因子
那么一个数可以划分为两种形式

1. $1×c$
2. $a×b$

然后对于每一个数，在两个因数之间连边，那么答案就是图中的最小环
但是如果要求每一个点所在的最小环，复杂度是$n^2$的，显然不行
令$m=\sqrt{max(a_i)}$，那么对于大于$m$的数之间是肯定没有边的
也就是说，最小环上的点一定有$≤m$的
所以只需要对$≤m$的点进行一遍BFS就行了

样例输入

3
6 15 10

样例输出

3

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

int n;
int vis[N],dis[N];
vector<int>a,us,e[N];

int init(int x) {
    for(int i=2; i*i<=x; i++) {
        if(x%i==0) {
            int cnt=0;
            while(x%i==0) {
                cnt++;
                x/=i;
            }
            if(cnt&1)
                x*=i;
        }
    }
    return x;
}

int bfs(int s) {
    for(auto i:us) {
        dis[i]=INF;
        vis[i]=0;
    }
    queue<int>q;
    dis[s]=0;
    q.push(s);
    int ans=INF;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(auto v:e[u]) {
            if(dis[v]>dis[u]+1) {
                dis[v]=dis[u]+1;
                vis[v]=1;
                q.push(v);
            } else if(vis[v]) {
                ans=min(ans,dis[u]+dis[v]+1);
            }
        }
    }
    return ans;
}



int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n;
    for(int i=0; i<n; i++) {
        int x;
        cin>>x;
        a.push_back(init(x));
    }
    sort(all(a));
    a.erase(unique(all(a)),a.end());
    if(a[0]==1) {
        cout<<1<<endl;
        return 0;
    }
    if(a.size()<n) {
        cout<<2<<endl;
        return 0;
    }
    for(int i=0; i<n; i++) {
        int t1=a[i];
        int t2=1;
        for(int j=2; j*j<=a[i]; j++) {
            if(a[i]%j==0) {
                t1=j;
                t2=a[i]/j;
                break;
            }
        }
        us.push_back(t1);
        us.push_back(t2);
        e[t1].push_back(t2);
        e[t2].push_back(t1);
    }
    sort(all(us));
    us.erase(unique(all(us)),us.end());
    int ans=INF;
    for(int i=1; i<=1000; i++) {
        if(!e[i].empty())
            ans=min(ans,bfs(i));
    }

    cout<<(ans==INF?-1:ans)<<endl;



    return 0;
}