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

题面看这里

众所周知，一个题如果自称 “REAL Number Theory Problem”，那它一定是个图论题。

题目大意

给你一个长度为 \(n\)??? 的整数数组 \(a\)???，问最少从 \(a\)??? 中取出多少个数，满足它们的乘积是一个完全平方数。输出这个最少的数量?，不存在就输出 -1。

\((1\leq n\leq1e5,~1\leq a_i\leq1e6)\)?

题目分析

乍一看感觉根本没法做，不过注意到有个很关键的条件：“every element in this array has at most 7 divisors”，也就是说数组的每个元素 \(a_i\) 最多有 7 个因数，我们来根据因数数量分类讨论一下：

为奇数：只有完全平方数的因数数量才能为奇数，所以 \(a_i\)? 本身就是一个完全平方数，此时直接输出 1 即可；

为 2：显然 \(a_i\) 是一个质数，\(a_i=p_1\)；

为 4：有两种可能，\(a_i=p_1*p_2 \or a_i=p_1^3\)；

为 6：有两种可能，\(a_i=p_1*p_2^2\or a_i=p_1^5\)??。

注意到几个数的平方因子对它们的乘积是否为完全平方数是没有任何影响的，因此我们可以合并一些情况，再特判掉存在完全平方数的情况，最终只剩下两种类型的元素：\(a_i=p_1*p_2\or a_i=p1\)???????。

接下来怎么做呢？我们举几个例子推一推：

\(a=\{2\times3,~3\times5,~5\times2\}\)???，答案为 3；

\(a=\{2\times3,~3\times5,~5\times7,~7\times2\}\)??，答案为 4；

\(a=\{1\times2,~2\times3,~3\times5,~5\times7,~7\times1\}\)??，答案为 5。

很容易看出来，在每个数的不同质因子个数不超过 2 的情况下，要让它们的乘积是一个完全平方数，只需让这几个数能够“首尾相连”即可，这就将问题转化为了在一张图上求最小环，我们可以用 bfs 在 \(O(n^2)\)?? 的时间内求解。

怎么建图呢？对于上述的两种类型的元素，如果 \(a_i=p_1*p_2\)????????，就 add(p1,p2)；否则就 add(p1,1)（双向边哈）。然后就从小到大地枚举图上的每个点，以其为起点跑一遍 bfs 找最小环即可，一个环都找不到则输出 -1。

然后虽然题目时间给了 3s，但 \(1e5\)????????? 的数据范围跑 \(n^2\)????????? 还是有点悬的，注意到对于图上任意的某个点 \(st\)，如果它大于 \(\sqrt{\max\{a\}}\)?????????，则不用讨论它，稍微证明一下：

设跟 \(st\)?? 直接相连的点为 \(ed\)??，因为 \(st>\sqrt{\max\{a\}}\)??，所以一定有 \(ed??，那么 \(ed\)?? 一定已经找过最小环了，此时：
1、如果全部的 \(ed\) 都找不到最小环，那么显然 \(st\) 也找不到；
2、如果某个 \(ed\)? 找到了最小环，且 \(st\)? 在这个最小环中，那么以 \(st\)? 为起点找到的最小环一定就是这个 \(ed\) 找到的最小环；
3、如果某个 \(ed\) 找到了最小环，且 \(st\) 不在这个最小环中，那么以 \(st\) 为起点一定找不到更小的环了，因为以这个 \(ed\) 为起点找最小环时就已经遍历了跟它直接相连的 \(st\) 的所有点了。其实只要想清楚这点就够了
综上，以 \(st\) 为起点再找一次最小环，对最终答案不会有任何影响，所以可以不做讨论。

所以我们不用遍历图上的每个点，只需遍历 \(1-\sqrt{\max\{a\}}\)??? 最多 \(\sqrt n\)??? 个点即可，时间复杂度 \(O(n\sqrt n)\)??????，可做！

代码实现

#include
using namespace std;
const double PI=acos(-1.0);const double eps=1e-6;const long long inf=LLONG_MAX;const int mod=1e9+7;const int maxn=1e6+5;
long long n,m,k,q,d,flag,cnt,num,sum,ans,maxx,minn,_=1;
bool vis[maxn];
int prime[maxn];
int mmp[maxn]; 
int f[maxn];
int head[maxn];
int dis[maxn];
int ent;
struct Edge{
	int last,v;
}a[maxn];
struct edge{
	int from,v;
}e[maxn];
struct Node{
	int id,cnt,f; 
};
set st;
int mp[maxn];
void init(){
	head[1]=-1;
	dis[1]=-1;
	for(int i=2;i1){
		f[cnt++]=a[x].v;
		x=a[x].last;
	}
	if(cnt==1){
		st.insert(f[0]);
		add(f[0],1);
	}
	else {
		if(f[0]*f[x]==t){
			st.insert(f[0]);
			st.insert(f[1]);
			add(f[0],f[1]);
		}
		else if((long long)f[0]*f[0]*f[1]==t){
			st.insert(f[1]);
			add(f[1],1);
		}
		else {
			st.insert(f[0]);
			add(f[0],1);
		}
	}
}
void bfs(int s){
	queue q;
	q.push({s,1,0});
	memset(dis,0,sizeof(dis)); 
	while(!q.empty()){
		Node now=q.front();
		q.pop();
		int id=now.id;
		int cnt=now.cnt;
		int f=now.f;
		dis[id]=cnt;
		for(int i=head[id];~i;i=e[i].from){
			if(e[i].v==f) continue;
			if(dis[e[i].v]!=0){
				if(dis[e[i].v]+dis[id]-1> n;
	for(int i=1;i<=n;i++){
		cin >> x;
		maxx=max(maxx,x);
		sq=sqrt(x);
		if(sq*sq==x){
			cout << 1;
			return 0;
		}
		getc(x);
	}
	for(auto x:st){
		if(x*x>maxx) break;
		bfs(x);
	}
	if(ans==1e9)
	cout << -1;
	else cout << ans;
}

稍微解释一下代码，init() 函数线性筛出素数和素数的最小质因子，使得接下来对 \(a_i\)? 的质因数分解可以做到 \(O(1)\)?我将其称为无敌质因数分解筛，算是一个时间上的小优化，当然普通地分解质因数也不会 \(T\)? 就是了?。

输入的时候特判某个元素为完全平方数的情况，顺带找到数组中最大的数 \(maxx\)???????，同时对每个元素进行质因数分解，连边建图并把点存入 set st 中，记得提前把 1 存进去嗷。

接下来只需以 st 中的每个数为起点 bfs 找最小环，大于 \(\sqrt {maxx}\)? 时直接 break 即可。