CF1325E. Ehab's REAL Number Theory Problem

发表于 | 阅读数

给一个长度为$n$的数组，每个数最多有7个因数，从中取$len$个数，使他们的乘积是平方数，求最小$len$。

考虑到因数格式。所以$a_i=p^x*q^y$或者$a_i=p^x$
且$q^x=q^{x\%2}$,如果是平方数那么就是一定是$(p\times q)\times (q\times z)\times (z\times p),(1\times p)\times (p\times q)\times (q\times 1)$.那么将$p-q$连接起来或者$1-p$连接起来。当构成一个环就可以构成平方数。求一个最小环($n^2$),又因为环里一定存在$p\leq\sqrt {a_i}$。只需要搜索$\sqrt {a_i}$个点。

时间复杂度$O(MAX(a_i))$

代码 
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int M = 1e6 + 10;

vector<int> g[M];
map<int, int> mp;
void div(int x)
{
    vector<int> s;
    if (mp[x])
    {
        puts("2");
        exit(0);
    }
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            int cnt = 0;
            while (x % i == 0)
                x /= i, cnt++;
            if (cnt & 1)
                s.push_back(i);
        }
    }
    if (x > 1)
        s.push_back(x);
    if (s.size() == 0)
    {
        puts("1");
        exit(0);
    }
    if (s.size() == 2)
    {

        g[s[0]].push_back(s[1]);
        g[s[1]].push_back(s[0]);
    }
    if (s.size() == 1)
    {
        g[s[0]].push_back(1);
        g[1].push_back(s[0]);
    }
}
int n;
int dis[M];
int ans = 1e9;
void bfs(int s)
{
    queue<pii> q;
    q.push(mk(s, 0));
    memset(dis, -1, sizeof(dis));
    dis[s] = 0;
    while (!q.empty())
    {
        int x = q.front().first;

        int fa = q.front().second;
        q.pop();

        for (int to : g[x])
        {

            if (to == fa)
                continue;
            if (dis[to] == -1)
            {
                dis[to] = dis[x] + 1;
                q.push(mk(to, x));
            }
            else
            {
                ans = min(ans, dis[x] + dis[to] + 1);
            }
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        div(x);
    }
    for (int i = 1; i * i <= M; i++)
        if (g[i].size())
            bfs(i);

    printf("%d\n", ans == 1e9 ? -1 : ans);
}