题意：给出n个数$(n<=1e5)$，每个数不大于1e6，保证每个数因子数不多于7个，求一个最短的子串，使其积为某数的完全平方数。
解题思路：做梦都没想到这是个图论的题。因子数不超过7个，说明每个数素因子最多两个，而若该数为素因子平方的倍数，可以将忽略，如27可以直接视为3，对结果不产生影响。因此，可以将每个数分解为两个素数之积，或一个素数。将每个数的两个素因子之间连一条边，若只有一个素因子则和1之间连一条边，最后找一个最小环即可。例如样例6,15,10，对于6会在2,3之间连边，15会在3,5之间连边，10会在2,5之间连边，这样的话会在2,3,5之间存在一个大小为3的环。
而对于最终的答案，其所在环必然有一个点小于1000，因为$1000^{2}=1e6$，必不可能存在某数两个因子都大于1000，所以枚举1-1000中的素数和1为起点，找出最小环即可。而对于最小环，直接进行bfs搜索，当搜到某点时，若该点已经被访问过，则表示可以行成一个环，更新答案即可。时间复杂度$O(nsqrt{n}+1000n)$，给了3秒足够。
贴上代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <ll,ll> pii; #define rep(i,x,y) for(int i=x;i<y;i++) #define rept(i,x,y) for(int i=x;i<=y;i++) #define per(i,x,y) for(int i=x;i>=y;i--) #define all(x) x.begin(),x.end() #define pb push_back #define fi first #define se second #define mes(a,b) memset(a,b,sizeof a) #define mp make_pair #define dd(x) cout<<#x<<"="<<x<<" " #define de(x) cout<<#x<<"="<<x<<" " #define debug() cout<<"I love Miyamizu Mitsuha forever. " const int inf=0x3f3f3f3f; const int maxn=1e5+5; const int maxm=1e6+5; int head[maxm],to[maxm<<1],nex[maxm<<1],tot=0; int a[maxn]; int prime[100000],cnt=0; bool vis[maxm]; void add(int a,int b) { to[tot]=b;nex[tot]=head[a];head[a]=tot++; to[tot]=a;nex[tot]=head[b];head[b]=tot++; } queue<pii> q; int dis[maxm]; int bfs(int st) { mes(dis,-1); while(!q.empty()) q.pop(); q.push(mp(st,-1)); dis[st]=0; int ans=inf; while(!q.empty()) { int point=q.front().fi,e=q.front().se^1; q.pop(); for(int j=head[point];j!=-1;j=nex[j]) { if(j==e) continue; if(dis[to[j]]!=-1) { ans=min(ans,dis[to[j]]+dis[point]+1); continue; } dis[to[j]]=dis[point]+1; q.push(mp(to[j],j)); } } return ans; } void solve(int n) { mes(vis,0); vis[1]=1; rept(i,2,n) { if(!vis[i]) { prime[cnt++]=i; } rep(j,0,cnt) { if(i*(ll)prime[j]>n) break; vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); mes(head,-1); int n; cin>>n; solve(1000000); rep(i,0,n) cin>>a[i]; rep(i,0,n) { rep(j,0,cnt) { if(a[i]%prime[j]==0) { ll s=(ll)prime[j]*prime[j]; while(a[i]%s==0) a[i]/=s; if(a[i]%prime[j]==0) { s=sqrt(a[i]/prime[j]); if(s*s==a[i]/prime[j]) add(1,prime[j]); else add(prime[j],a[i]/prime[j]); } else add(1,a[i]); break; } if(a[i]/prime[j]<prime[j]) { add(1,a[i]); break; } } } int ans=inf; rep(i,1,1000) if(!vis[i]||i==1) ans=min(ans,bfs(i)); if(ans==inf) cout<<"-1 "; else cout<<ans<<" "; return 0; }