Codeforces Round #628 (Div. 2) E. Ehab's REAL Number Theory Problem

思路：因为不超过7个因数，所有至多有2个不同的质因子。
我们先把一些特殊的情况处理掉：
1.输入包含完全平方数
2.存在两个数相乘是完全平方数
那么剩下的情况 答案必然是>=3
预处理出所有数的：幂次为奇数的质因子，如果仅有一个的话，就给这个质因子打个标记，否则将两个质因子连一个无向边。
那么如果存在解的话，必然分成两种情况：一条路径且两端的点被打了标记；一个环。
由于输入数的大小在1e6级别，所以求得答案的路径上必然存在一个数<=1000。
所以枚举环上的点跑bfs，判一判存不存在上述两种情况。然后取一个最优解。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
#define fi first
#define se second
#define pb push_back
int n,a[N],p[N],b[N],cnt;
void P(){
  for(int i=2;i<N;i++){
    if(!p[i])b[++cnt]=i;
    for(int j=1;j<=cnt&&1ll*b[j]*i<N;j++){
      p[b[j]*i]=1;
      if(i%b[j]==0)break;
    }
  }
}
int co[N],vis[N];
vector<int>G[N];
int pri[N],so,dis[N],res[N];
int Q[N],sa[N];
int main() {
  ios::sync_with_stdio(false);
  cin>>n;P();
  for(int i=1;i<=n;i++){
    cin>>a[i];sa[a[i]]++;
    if(a[i]==1)return cout<<1,0;
    vector<pair<int,int>>v;
    int y=a[i];
    for(int j=1;1ll*b[j]*b[j]<=y&&j<=cnt;j++){
      if(y%b[j]==0){
        int num=0;
        while(y%b[j]==0){
          y/=b[j];
          num++;
        }
        if(num&1)v.pb({b[j],num});
      }
    }
    if(y>1)v.pb({y,1});
    if(!v.size())return cout<<1,0;//自己就是完全平方数
    if(v.size()==1){
      vis[v[0].fi]=1;
      pri[++so]=v[0].fi;
      co[v[0].fi]++;
    }else if(v.size()==2){
      G[v[0].fi].pb(v[1].fi);
      G[v[1].fi].pb(v[0].fi);
      pri[++so]=v[0].fi;
      pri[++so]=v[1].fi;
      co[v[0].fi*v[1].fi]++;
    }
  }
  for(int i=1;i<=1000000;i++)if(co[i]>=2 )return cout<<2,0;//存在两个数相乘为完全平方数
  int ans=n+1;
  for(int i=1;i<=1000;i++)if(G[i].size()){
      for(int j=1;j<=so;j++)res[pri[j]]=-1,dis[pri[j]]=n+1;
      dis[i]=0;
      res[i]=0;
      int idx=0;
      Q[++idx]=i;
      int le=n+1,ri=n+1;
      for(int j=1;j<=idx;j++){
        if(vis[Q[j]] && Q[j]!=i){//找到最近的打标记的点
          if(dis[Q[j]]<le){
            swap(le,ri);
            le=dis[Q[j]];
          }else if(dis[Q[j]]<ri){
            ri=dis[Q[j]];
          }
        }
        for(auto k:G[Q[j]]){
          if(res[k]!=-1 ){
            if(k!=Q[j] && dis[k]>=dis[Q[j]])ans=min(ans,dis[k]+dis[Q[j]]+1);//找到最小环
            continue;
          }
          dis[k]=dis[Q[j]]+1;
          res[k]=0;
          Q[++idx]=k;
        }
      }
      if(vis[i]){
        ans=min(ans,le+2);
      }else{
        ans=min(ans,le+ri+2);
      }
    }
  if(ans==n+1)cout<<-1<<'\n';
  else {
    cout<<ans<<'\n';
    assert(ans!=2);
  }
  return 0;
}