# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
84376667 |
Practice:
JKLover |
1325E
- 15
|
C++17 (GCC 7-32)
|
Accepted
|
779 ms
|
42788 KB
|
2020-06-20 06:21:12 |
2020-06-20 06:21:12 |
|
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out = 0, fh = 1;
char jp = getchar();
while ((jp > '9' || jp < '0') && jp != '-')
jp = getchar();
if (jp == '-')
fh = -1, jp = getchar();
while (jp >= '0' && jp <= '9')
out = out * 10 + jp - '0', jp = getchar();
return out * fh;
}
void print(int x)
{
if (x >= 10)
print(x / 10);
putchar('0' + x % 10);
}
void write(int x, char c)
{
if (x < 0)
putchar('-'), x = -x;
print(x);
putchar(c);
}
const int N = 1e6 + 10;
int n, dis[N], ism[N], cnt = 0, prime[N], mi[N], stk[N], tp = 0;
int used[N], su[N], k = 0;
void Sieve(int mx)
{
ism[1] = 1;
for (int i = 2; i <= mx; ++i)
{
if (!ism[i])
{
prime[++cnt] = i;
mi[i] = i;
}
for (int j = 1; j <= cnt && i * prime[j] <= mx; ++j)
{
ism[i * prime[j]] = 1;
mi[i * prime[j]] = prime[j];
if (i % prime[j] == 0)
break;
}
}
}
vector<pair<int, int> > G[N];
queue<int> q;
int main()
{
n = read();
Sieve(1000000);
int m = 0;
for (int i = 1; i <= n; ++i)
{
int v = read(), x = 1, y = 1;
while (v > 1)
{
int p = mi[v], t = 0;
while (v % p == 0)
v /= p, t ^= 1;
if (t & 1)
{
if (x == 1)
x = p;
else if (y == 1)
y = p;
else
assert(false);
}
}
++m;
G[x].push_back(make_pair(y, m)), G[y].push_back(make_pair(x, m));
}
memset(dis, -1, sizeof dis);
prime[0] = 1;
int ans = n + 1;
for (int i = 0; i <= cnt && prime[i] <= 1000; ++i)
{
while (tp)
dis[stk[tp--]] = -1;
while (k)
used[su[k--]] = 0;
int s = prime[i];
dis[s] = 0, q.push(s), stk[++tp] = s;
while (!q.empty())
{
int x = q.front();
q.pop();
if (dis[x] + 1 >= ans)
continue;
for (auto tmp : G[x])
if (!used[tmp.second])
{
int y = tmp.first;
if (dis[y] != -1)
ans = min(ans, dis[x] + dis[y] + 1);
else
{
dis[y] = dis[x] + 1;
q.push(y), stk[++tp] = y;
used[tmp.second] = 1, su[++k] = tmp.second;
}
}
}
}
if (ans > n)
puts("-1");
else
write(ans, '\n');
return 0;
}
Click to see test details