Codeforces Round #628 (Div. 2) 一道过于暴力的 搜索 题。

题目链接：Codeforces 1325E。

系列题解：
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd；
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy；
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs；
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist；
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem；
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。

题目

原题

题意简述

给一些数，每个的因数个数不超过 $7$，求最少选出多少个，使得乘积为完全平方。无解输出 $-1$。

数据范围

$$1\leq n\leq 10^5$$

$$1\leq a_i\leq10^6$$

时空限制

见原题 pdf 文件。

题解

思路

分解每一个 $a_i$，如果是完全平方或者可以配对的，答案为 $1$ 或 $2$，否则就直接暴搜索答案，答案不可能超过 $10^3$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

const int MAXN=1000000+5;

int n;
int a[MAXN];
int ans=INF;
vector<pair<int,int>/**/> V[MAXN];
map<pair<int,int>,int> M;

void Div(int x,int y){
	reg int p=1,q=1;
	for(int i=2;i*i<=x;++i){
		if(x%i==0){
			reg int flag=0;
			while(x%i==0)
				x=x/i,flag^=1;
			if(!flag)
				continue;
			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;
	}
	++M[make_pair(p,q)];
	if(M[make_pair(p,q)]>1){
		ans=min(ans,2);
		return;
	}
	V[p].push_back(make_pair(q,y));
	V[q].push_back(make_pair(p,y));
	return;
}

bool vis[MAXN];
int dep[MAXN];
queue<int> Q;

inline int BFS(int x){
	if(V[x].empty())
		return INF;
	memset(vis,false,sizeof(vis));
	memset(dep,0,sizeof(dep));
	while(!Q.empty())Q.pop();
	dep[x]=1,Q.push(x);
	while(!Q.empty()){
		reg int ID=Q.front();
		Q.pop();
		for(reg int i=0;i<(int)V[ID].size();++i){
			if(vis[V[ID][i].second])
				continue;
			if(dep[V[ID][i].first])
				return dep[V[ID][i].first]+dep[ID]-1;
			vis[V[ID][i].second]=true;
			dep[V[ID][i].first]=dep[ID]+1;
			Q.push(V[ID][i].first);
		}
	}
	return INF;
}

int main(void){
	n=read();
	for(reg int i=1;i<=n;++i){
		a[i]=read();
		Div(a[i],i);
	}
	if(ans!=INF){
		printf("%d\n",ans);
		return 0;
	}
	for(reg int i=1;i<=1000;++i)
		ans=min(ans,BFS(i));
	if(ans==INF)
		puts("-1");
	else
		printf("%d\n",ans);
	return 0;
}