Ehab's REAL Number Theory Problem
题目描述
You are given an array $ a $ of length $ n $ that has a special condition: every element in this array has at most 7 divisors. Find the length of the shortest non-empty subsequence of this array product of whose elements is a perfect square.
A sequence $ a $ is a subsequence of an array $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) elements.
输入格式
The first line contains an integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of $ a $ .
The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , $ \ldots $ , $ a_{n} $ ( $ 1 \le a_i \le 10^6 $ ) — the elements of the array $ a $ .
输出格式
Output the length of the shortest non-empty subsequence of $ a $ product of whose elements is a perfect square. If there are several shortest subsequences, you can find any of them. If there's no such subsequence, print "-1".
样例 #1
样例输入 #1
3
1 4 6
样例输出 #1
1
样例 #2
样例输入 #2
4
2 3 6 6
样例输出 #2
2
样例 #3
样例输入 #3
3
6 15 10
样例输出 #3
3
样例 #4
样例输入 #4
4
2 3 5 7
样例输出 #4
-1
提示
In the first sample, you can choose a subsequence $ [1] $ .
In the second sample, you can choose a subsequence $ [6, 6] $ .
In the third sample, you can choose a subsequence $ [6, 15, 10] $ .
In the fourth sample, there is no such subsequence.
至多7个因子是什么条件？仔细分析，其实是说明这个数至多有两个不同质因数。
要求一个序列的所有数相乘为完全平方。也就代表任意一个质因数的次数之和为偶数。那么在某一个数中，如果有一个质因数出现了偶数次，那他很没用，出现了和没出现一个样，我们就可以不理他。然后现在要求选出来的序列每种质因数出现偶数次，会想到一件事。如果有一个数的质因数是 \((u,v)\)，那么就一定需要一个含有 \(u\) 的数和一个含有 \(v\) 的数，然后往后又要推。最后一定是一个环。所以考虑最小环构图。
构图很简单，如果存在一个数 \(a_i=u\times v\)（ \(u,v\) 为质数），那么就可以从 \(u\) 向 \(v\) 连一条无向边。如果一个数次数为奇数的质因数只有一个，那就把质因数 \(p\) 和 \(1\) 连边。
现在到了跑最小环。最小环问题解法可以使用 Floyd，但是这里完全行不通。注意到这里的边是无权的，对于最小环，有一种 \(O(n^2)\) 的算法。钦定一个一定在最小环上的点 \(x\)，用它跑出一棵 bfs 树。然后对于一条不在树上的边 \((u,v)\)，设点 \(x\) 到点 \(y\) 的最短路为 \(d_y\)，那么如果点 \(x\) 和点 \((u,v)\) 要同时在最小环上，最小环长为 \(d_u+d_v+1\)。
或许有人会问，如果点 \((u,v)\) 在 bfs 树上的 lca 不为点 \(x\)，怎么办？其实没关系，因为等我枚举 \(x\) 枚举到他们的 lca 时，自然就会把那个环算入了。
\(O(n^2)\) 的复杂度仍然不能接受，但发现不存在两个数 \(x,y\ge 1000\)，同时又有连边。这说明，最小环上一定有一个点 \(x\le1000\)。所以我们枚举在环上的点时只用枚举小于等于1000的质数就行了。
复杂度 \(O(\frac{n\sqrt{n}}{logn})\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int n,a[N],pri[M],hd[M],dp[M],q[M],l,r,ans=2000000000,e_num(1),pw[M];
vector<int>g[M];
struct edge{
int v,nxt,f;
}e[N<<1];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
void run(int x)
{
memset(dp,0,sizeof(dp));
dp[q[l=r=1]=x]=1;
for(int i=2;i<=e_num;i++)
e[i].f=0;
while(l<=r)
{
int k=q[l];
++l;
for(int i=hd[k];i;i=e[i].nxt)
{
if(!dp[e[i].v])
{
e[i^1].f=1;
dp[e[i].v]=dp[k]+1;
q[++r]=e[i].v;
}
else if(!e[i].f)
{
// printf("%d %d %d\n",x,k,e[i].v);
ans=min(ans,dp[k]+dp[e[i].v]-1);
}
}
}
}
int main()
{
for(int i=2;i<M;i++)
{
// printf("%d\n",i);
if(!pri[i])
{
for(int j=1;j*i<M;j++)
{
pri[j*i]=1;
if(j%i==0)
pw[j]=pw[j/i]^1;
if(!pw[j])
g[j*i].push_back(i);
}
for(int j=1;j*i<M;j++)
pw[j]=0;
}
}
// puts("hjhakioi");
// for(int i=1;i<M;i++)
// {
// printf("%d\n",i);
// for(int j=0;j<g[i].size();j++)
// printf("%d ",g[i][j]);
// putchar('\n');
// }
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
if(g[a[i]].size()==1)
{
add_edge(1,g[a[i]][0]);
add_edge(g[a[i]][0],1);
}
else if(g[a[i]].size())
{
add_edge(g[a[i]][0],g[a[i]][1]);
add_edge(g[a[i]][1],g[a[i]][0]);
}
else
{
printf("1");
return 0;
}
}
for(int i=1;i<=1000;i++)
run(i);
if(ans>n)
printf("-1");
else
printf("%d",ans);
}