0%

CF1325E

题意:给一个长为$n$的正整数序列,每个数至多有$7$个约数,要你选出一个乘积为完全平方数的最短子序列,输出长度即可

$n\le 10^5,a_i\le 10^6$

每个数至多有$7$个约数$\rightarrow$ 每个数至多两个不同的质因数

  • 如果某个数没有指数为奇数的质因子,那么它就是一个完全平方数,输出1即可
  • 如果某个数有1个指数为奇数的质因子,让这个质因子和虚点1连无向边。
  • 某个数有两个指数为奇数的质因子,让这两个质因子间连无向边

问题等价于,求该无向图中的最小环。

常用的求最小环方法是Floyd,但时间复杂度$\mathcal O(n^3)$显然无法接受。注意到所有边权均为1的性质,可以使用bfs最小环:枚举点作为起点,然后bfs,如果下一个点$v$不是现在点$u$的前驱:如果$v$没有被访问过,那么记录距离,放入队尾(并记录其前驱是$u$),否则更新答案。

这样的时间复杂度仍是$\mathcal O(nV)$,无法接受。无法接受

考虑$x> \sqrt V$,有$x^2>V$,即超过$\sqrt V$的素数不可能被考虑超过1次,于是不需要把这些点作为起点。

时间复杂度$\mathcal O(n\sqrt V)$

找出素因子那里,直接每次$\sqrt V$做就好,不用预处理了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#define MAXN 1000011
struct Edge
{
ll v,nxt;
}e[MAXN<<1|1];
ll cnt=0,last[MAXN],pre[MAXN],dis[MAXN];
void adde(ll u,ll v)
{
e[++cnt].v=v;
e[cnt].nxt=last[u],last[u]=cnt;
}
ll ans=INF;
void bfs(ll s)
{
static std::queue<ll>q;
memset(dis,0,sizeof dis);
//printf("work %lld:\n",s);
dis[s]=1,pre[s]=0;
q.push(s);
while(!q.empty())
{
ll u=q.front();q.pop();
//printf("dis[%lld]=%lld,pre=%lld\n",u,dis[u],pre[u]);
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(v==pre[u])continue;
if(!dis[v])
{
dis[v]=dis[u]+1,pre[v]=u;
q.push(v);
}
else umin(ans,dis[u]+dis[v]-1);
}
}
}
bool is_prime(ll n)
{
for(ll i=2;i*i<=n;++i)
if(n%i==0)return 0;
return 1;
}
int main()
{
ll n=read();
for(ll i=1;i<=n;++i)
{
ll x=read(),c1=0,c2=1;
for(ll j=2;j*j<=x;++j)
if(x%j==0)
{
ll t=0;
while(x%j==0)++t,x/=j;
if((t&1))
{
if(!c1)c1=j;
else c2=j;
}
}
if(x>1)
{
if(!c1)c1=x;else c2=x;
}
//printf("c1=%lld c2=%lld\n",c1,c2);
if(!c1)
{
puts("1");return 0;
}
adde(c1,c2),adde(c2,c1);
}
bfs(1);
for(ll i=2;i<=1000;++i)
{
if(is_prime(i))bfs(i);
}
if(ans>n)puts("-1");
else printf("%lld",ans);
return 0;
}