一道有意思的毒瘤题
题意
给出数列\(\{a_1,a_2,...,a_n\}\),其中每个\(a_i\)最多只有7个因子.求乘积为完全平方数的最短子序列
\(1 \leq n \leq 1e5\),\(1 \leq a_i \leq 1e6\)
思路
首先条件里"最多只有7个因子"是很有意思的一个提示,它实际上是指每个数最多只有2个素因子
证明:
我们考虑因子个数定理:
以\(d(N)\)表示\(N\)的因子个数,且\(N = Σ_{i=1}^{n}p_{i}^{k_i}\)
则有\(d(N) = \prod_{i = 1}^{n}(k_i+1)\)
容易看出当\(N\)有3个素因子时,\(d(N) \geq 8\).故N最多只有两个素因子.
如此可以分解每个\(a_i\)为\(a_i = p^{k_1}q^{k_2}\)的形式.因为我们需要求完全平方数,\(k_1,k_2\)可以直接模2.之后有如下三种情况:
- \(a_i = 1\)
- \(a_i = 1*p_i\)
- \(a_i = p_i*q_i\) 我们要做的就是保证子序列里每个\(p_i,q_i\)的指数为偶数,同时使这个序列最短.
如何高效求解这个问题?上面的因子分解得到了\(p,q\)两个因子,让人联想到图的连边.不妨如此建模:将因子作为点,向\(a_i\)的两个因子\(p_i,q_i\)连一条无向无权边,则问题转化为求这个图里的最小环.(因为一个简单环里每个点的度数都为2,满足每个因子的指数都为偶数这一要求).
对于无向无权图图求最小环我们可以简单地对每个点做BFS.对于一条未访问的边\(u,v\) ,如果\(v\)已访问过,那么该图存在一个长度为\(dis[u]+dis[v]+1\)的环(请自己画图验证).但是这样复杂度为\(O(n^2)\)
考虑这个图的特殊性质:任意正整数\(N\)最多只有一个大于\(\sqrt{N}\)的素因子,换句话说这个图里每条边都至少有一个点标号小于\(\sqrt{max\{a_i\}}\).只需枚举这些点即可.
总复杂度:\(O(\sqrt{max{a_i}}n)\)
代码
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
81
82
83
84
85
86
87
88
89
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
const int maxm = 1e7+10;
struct Edge{
int f,t,next;
Edge(int f = 0,int t = 0,int next = 0):f(f),t(t),next(next){}
}edge[maxn];
int cnt,head[maxn],dis[maxn],ans = 1e9;
void addedge(int f,int t){
edge[cnt] = Edge(f,t,head[f]);
head[f] = cnt++;
}
void add(int f,int t){
addedge(f,t);
addedge(t,f);
}
bool visp[maxn],vis[maxn];
vector<int>P,d[maxn];
int n,raw[maxn];
void init(){
visp[1] = 1;
for(int i = 2;i < maxn;i++)if(!visp[i]){
for(int j = i*2;j < maxn;j+=i)visp[j] = 1;
}
for(int i = 2;i < maxn;i++)if(!visp[i]){
P.push_back(i);
}
cin >> n;
for(int i = 1;i <= n;i++){
cin >> raw[i];
int cur = raw[i];
if(!visp[cur]){
d[i].push_back(cur);
continue;
}
for(int j = 2;j*j <= raw[i];j++){
int cnt2 = 0;
while(cur%j == 0){
cur /= j;cnt2++;
}
if(cnt2%2)d[i].push_back(j);
}
if(cur > 1)d[i].push_back(cur);
}
for(int i = 1;i <= n;i++){
if(!d[i].size()){
cout << 1;
exit(0);
}
else if(d[i].size() == 1){
add(1,d[i][0]);
}
else add(d[i][0],d[i][1]);
}
}
void BFS(int s){
memset(dis,-1,sizeof(dis));
dis[s] = 0;
queue<pair<int,int> >q;
q.push(make_pair(s,0));
while(!q.empty()){
auto now = q.front();
q.pop();
int u = now.first,fa = now.second;
for(int i = head[u];~i;i = edge[i].next){
int v = edge[i].t;
if(v == fa)continue;
if(dis[v] == -1){
dis[v] = dis[u]+1;
q.push(make_pair(v,u));
}
else{
ans = min(ans,dis[v]+dis[u]+1);
}
}
}
}
int main(){
memset(head,-1,sizeof(head));
init();
for(int i = 1;i <= 1010;i++)BFS(i);
if(ans == 1e9)ans = -1;
cout << ans;
return 0;
}
|
\(2^{2n-1}+2^{2n-2}-2^n\)